Пройдите по массиву с конца, поддерживая текущий максимум (индекс imax
) от k+1
-го элемента до конца массива, и вычисляя наилучшую разность p[imax]-p[k]
, обновляйте максимум текущей выгоды, и записывайте эти значения во вспомогательный массив V
. Таким образом, V[k]
будет описывать лучшее вложение начиная с k
-го элемента до конца.
Теперь пройдите от начала, поддерживая текущий минимум (индекс imin
) от начала массива до j-1
элемента, вычисляя наилучшую разность p[j]-p[imin]
c учётом вложения одного рубля, поддерживая максимум лучшего вложения Best
от начала до k
-го элемента, и комбинируйте текущий максимум с V[k+1]
, запоминайте лучшее значение Best*V[k+1]
Алгоритм линейный