121. Best Time to Buy and Sell Stock - cocoder39/coco39_LC GitHub Wiki

121. Best Time to Buy and Sell Stock

supposing you are going to sell stock at each time you visit a num, so your problem is when to buy a stock. Obviously, if you want to sell stock at time i, you need buy stock at a time j where prices at j is lowest from time 0 to time i.

On earth it is max subarray problem. Given prices {1, 7, 4, 11}, the problem is equal to find out max subarry from {0, 6, -3, 7}.

int maxProfit(vector<int>& prices) {
        if (prices.empty()) {
            return 0;
        }
        
        int lowest = prices[0];
        int res = 0;
        for (int i = 0; i < prices.size(); i++) {
            lowest = min(lowest, prices[i]);
            res = max(res, prices[i] - lowest);
        }
        return res;
    }

public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        
        int len = prices.length;
        int buyPrice[] = new int[len];
        buyPrice[0] = Integer.MAX_VALUE;

        int res = 0;
        for (int i = 1; i < len; i++) {
            buyPrice[i] = Math.min(buyPrice[i - 1], prices[i-1]);
            res = Math.max(res, prices[i] - buyPrice[i]);
        }
        return res;
    }
⚠️ **GitHub.com Fallback** ⚠️