Автор | Сообщение |
|
Отправлено: 27.11.20 08:36. Заголовок: Задача 27-19(81) Алгоритм решения
Здравствуйте! Объясните пожалуйста алгоритм решения данной задачи. Сама задача: Имеется набор данных, состоящий из целых чисел. Необходимо определить максимальное произведение подпоследовательности, состоящей из одного или более смежных элементов. Программа: 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() За что отвечают переменные dp_min и dp_max? Спасибо.
|
|
|
Новых ответов нет
[см. все]
|
|
|
Отправлено: 21.06.21 19:31. Заголовок: Попробуй решить эту ..
Попробуй решить эту задачу при 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]) Отсюда и следуют эти переходы в решении.
|
|
|