[Leetcode] Best Time to Buy and Sell Stock III

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

因为我们可以买无限多的股票，因此我们应该在合适的时候及时出手，我们可以分析一下几种简单的情况：

1. 输入为1，2，3，4的时候，显然我们应该在最后的时候卖掉
2. 输入为1，3，2，4的时候，显然我们应该在3和4的时候卖掉
3. 输入为4，3，2，1的时候，显然我们不可能卖得出去，其实可以等效成我们当天买了但是又直接卖掉了

因此我们只需要找到输入中的连续递增子串然后求出首尾的差，就是我们所能得到的最大profit了。在实现的时候注意当到达最后一天的时候，我们可能还一直没有卖出（一直递增），所以最后应该强行卖出股票，即使强行卖出，也能保证收回来的钱不小于0。

    public int maxProfit(int[] prices) {
        int n = prices.length;
        if(n == 0 || n == 1) return 0;
        int profit = 0, current = prices[0];
        
        for(int i = 0; i < n-1; i++) {
            if(prices[i] > prices[i+1]) {
                profit = profit + prices[i] - current;
                current = prices[i+1];
            }
        }
        profit = profit + prices[n-1] - current;
        
        return profit;
    }