Форум » Обработка числовых последовательностей » Задача 27-19(81) Алгоритм решения » Ответить
Задача 27-19(81) Алгоритм решения
dkonyashkin: Здравствуйте! Объясните пожалуйста алгоритм решения данной задачи. Сама задача: Имеется набор данных, состоящий из целых чисел. Необходимо определить максимальное произведение подпоследовательности, состоящей из одного или более смежных элементов. Программа: [pre2] Fin = open("27.txt") N = int( Fin.readline() ) x = int( Fin.readline() ) dp_min = dp_max = ma = x for i in range(N-1): x = int( Fin.readline() ) t = min( dp_min*x, min(dp_max*x, x) ) dp_max = max(dp_min*x, max(dp_max*x, x)) dp_min = t ma = max(ma, dp_max) # print(x, ma) print( ma ) Fin.close()[/pre2] За что отвечают переменные dp_min и dp_max? Спасибо.
Ответов - 1
Mike_Boone: Попробуй решить эту задачу при n = 3, n = 4, n = 5, ..., n = k. Очевидно, что задача на дп. 1. Произведение ряда из четного количества отрицательных чисел - четно. 2. Произведение ряда из положительных чисел, умноженное на отрицательное - по величине отрицательно. 3. Произведение ряда отрицательных чисел, умноженное на отрицательное - по величине положительно. Этого хватит, чтобы понять код. Пусть dp_max_i - самое большое произведение подпоследовательности среди первых i чисел(dp_max) dp_min_i - самое маленькое по величине произведение подпоследовательности первых i чисел (dp_min) Очевидно, что dp_max[ i] = max(dp_min[ i-1] * a[ i], dp_max[ i-1] * a[ i], a[ i]) dp_min[ i] = min(dp_min[ i-1] * a[ i], dp_max[ i-1] * a[ i], a[ i]) Отсюда и следуют эти переходы в решении.
полная версия страницы