Задача: "Знал бы прикуп...". Яндекс.Контест

Рейтинг: -4Ответов: 1Опубликовано: 07.02.2023

каким способом можно решить подобную задачу? Написал своё решение, но больно уж оно огромное и не проходит дальше 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]

Алгоритм линейный