Best Time to Buy and Sell Stock

Leetcode #121 | Easy | 1-D Динамика

Идея

Ставим левый указатель на 0 и идем по массиву правым. Если цена на левом меньше цены на правом, то можно зафиксировать прибыль - обновляем результат. Если же цена стала меньше либа равна, то двигаем левый указатель на место правого. Мы не может потерять никаких промежуточных сумм на этом действии, потому что в силу монотонности, никаие значения на (l,r) не удовлетворяли p[l]<p[r]

Big-O

• Время O(N)
• Память O(1)

Код

class Solution {
    public int maxProfit(int[] prices) {
        int res = 0;
        int l = 0;

        for (int r = 0; r < prices.length; r++) {
            if (prices[l] < prices[r]) {
                res = Math.max(res, prices[r]-prices[l]);
            } else {
                l = r;
            }
        }

        return res;
    }
}