Задача: "Знал бы прикуп...". Яндекс.Контест
каким способом можно решить подобную задачу? Написал своё решение, но больно уж оно огромное и не проходит дальше 5-го теста. Понимаю, что тут скорее всего есть какой-то алгоритм, но не могу к нему подойти.
Ответы (1 шт):
Пройдите по массиву с конца, поддерживая текущий максимум (индекс 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]
Алгоритм линейный