121. Best Time to Buy and Sell Stock.md

Solution1

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int curMax = 0, maxSoFar = 0;
        for (int i = 1; i < prices.length; i++) {
            curMax = Math.max(curMax + prices[i] - prices[i - 1], 0);
            maxSoFar = Math.max(curMax, maxSoFar);
        }
        return maxSoFar;
    }
}

note

• time O(n) space O(1)
• Iterate through the array once, each time update the min price in the array and max profit.