Best Time to Buy and Sell Stock

1. Best Time to Buy and Sell Stock

Leetcode 121 (M)
只能买卖一次。
只能一次的话，就是要寻找最小和最大的值（同时必须满足最大值在最小值后面）
可以用两个值来存,maxcurr记录对于第i天可以拿到的最大利润，maxsofar记录到目前为止见过的最大利润（最大的maxcurr)。
所以唯一的问题是如何计算maxcurr，如果maxcurr小于0，那么就是0，对于第i天的maxcurr来说，如果maxcurr + (p[i] - p[i-1]) > 0, 那么更新maxcurr。

或者可以，一直寻找最小的minprice，然后用prices[i]-minprice，同时即时更新minprice。

code1:

public class Solution {
    public int maxProfit(int[] prices) {
        int maxcurr = 0;
        int maxsofar = 0;
        for (int i = 1; i < prices.length; i++) {
            maxcurr = Math.max(0, maxcurr + (prices[i] - prices[i-1]));
            maxsofar = Math.max(maxsofar, maxcurr);
        }
        return maxsofar;
    }
}

code2:

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

1. Best Time to Buy and Sell Stock II

Leetcode 122 (M)

可以买卖多次。这样的话很容易理解，就是把所以递增的都增量都加起来就可以了。因为如果是递增，那么price[j] - price[k] = price[j]-price[i] + price[i]-price[k]

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

1. Best Time to Buy and Sell Stock III
2. Best Time to Buy and Sell Stock IV
3. Best Time to Buy and Sell Stock with Cooldown