Простая задача на динамическое программирование: Лучшее время для покупки и продажи акции

Задача.

Дан массив целых чисел prices, где prices[i] - цена на акцию в день i. Вам нужно максимизировать прибыль выбрав один день, когда вы купите одну акцию, а также другой день в будущем, когда вы продадите акцию. В качестве результата нужно вернуть максимальную прибыль, которую можно получить. Если прибыль получить нельзя, то вернуть 0.

Ссылка на leetcode: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/

Пример:
prices = [7,1,5,3,6,4]
Ответ: 5 (Купить по 1, продать по 6).

Решение.

Brute force.

Первое решение, которое приходит в голову, это перебрать все пары, посчитать для каждой прибыль и найти максимальную прибыль. Такое решение работает за O(n^2) по времени и O(1) по памяти.
Перебор пар можно сделать при помощи вложенного цикла:

for (int i = 0; i < prices.length; i++) {
    for (int j = i + 1; j < prices.length; j++) {
        ......
    }
}

Тогда прибыль для покупки в день i и продажи в день j:
int profit = prices[j] - prices[i];
И нам нужно найти максимум:

public int maxProfit(int[] prices) {
    int maxProfit = Integer.MIN_VALUE;
    for (int i = 0; i < prices.length; i++) {
        for (int j = i + 1; j < prices.length; j++) {
            maxProfit = Math.max(maxProfit, prices[j] - prices[i]);
        }
    }
    return maxProfit > 0 ? maxProfit : 0;
}

Dynamic Programming.

Можно ли улучшить это решение? Да, используя динамическое программирование. Давайте применим bottom-up подход. Для этого нужно разбить задачу на подзадачи, а также установить связь решения подзадач с решением более общей задачи.
В данном случае, такой подзадачей может быть максимальная прибыль, которую мы можем получить, если решим продавать в день i. Тогда решением общей задачи будет максимум из всех таких вариантов (максимум из прибылей, когда мы продаем в день 1, день 2, день 3 и т.д.). Как нам определить максимальную прибыль, которую мы можем получить, если продавать в день i? Очевидно, такая прибыль будет максимальная, когда мы купили в день с минимальной ценой в какой-то день до текущего дня i.

maxProfit(i) = prices[i] - min(prices[j], j = 0, .., i - 1)

Тогда ответ будет максимум из таких прибылей:

maxProfit = max(maxProfit(i), i = 1, .., n - 1)

Для того, чтобы нам снова и снова не перевычислять min(prices[j], j = 0, .., i - 1), мы можем хранить это в переменной minPriceSoFar и обновлять ее по мере итерации по массиву.
Код решения:

public int maxProfit(int[] prices) {
    int maxProfit = Integer.MIN_VALUE;
    int minPriceSoFar = Integer.MAX_VALUE;
    for (int i = 0; i < prices.length; i++) {
        minPriceSoFar = Math.min(minPriceSoFar, prices[i]);
        int currentProfit = prices[i] - minPriceSoFar;
        maxProfit = Math.max(maxProfit, currentProfit);
    }
    return maxProfit;
}

Решение работает за O(n) по времени и O(1) по памяти.