Отправлено: 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])

Отсюда и следуют эти переходы в решении.