leetcode[122]Best Time to Buy and Sell Stock II

问题：是leetcode[121]Best Time to Buy and Sell Stock的延伸，该题可以完成随意次交易，但是，要求一天内只能进行一种交易操作，而且，手里只能有一个股票（即先买入，再卖出，才可再买入）

输入：股票价格，数组prices[n]存放每天的股价。设置一个flag变量，1表示手里有股票，0表示手里没有股票。

输出：最大收益。

主要思想：greedy。在局部最低价（即当天价格低于前后两天的价格）买入，然后在局部最高价（即当天价格高于前后两天的价格）卖出。

正确性证明：如果不在局部最低价买入，则存在一种解（在局部最低价买入）具有更大收益；同理，也要在局部最高价卖出。

时间复杂度：O(n)

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int max_profit = 0;           //当前已获收益
        int minimum = INT_MAX;        //买入价格
        int flag=0;                   //flag表示手里是否有股票
        for(int i=0; i<prices.size(); i++)
        {
            if(prices[i]<minimum)
            {
                minimum = prices[i];
                flag = 1;   
            }
            else if((prices[i]>=prices[i-1])&&(flag==1))
            {
                if(i==prices.size()-1)
                {
                    max_profit = max_profit + prices[i]-minimum;
                }
                else if((prices[i]>prices[i+1])&&(flag==1))
                {
                    max_profit = max_profit + prices[i]-minimum;
                    flag = 0;
                    minimum = INT_MAX;
                }
            }
        }
        return max_profit;
    }
};

这里介绍一下[2]中的思想，如下图

时间复杂度：O(n)。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i = 0;
        int valley=prices[0];
        int peak=prices[0];
        int max_profit=0;
        while(i<prices.size()-1)
        {
            while(i<prices.size()-1&&prices[i]>=prices[i+1])
                i++;
            valley = prices[i];
            while(i<prices.size()-1&&prices[i]<=prices[i+1])
                i++;
            peak = prices[i];
            max_profit += peak-valley;
        }
        return max_profit;
    }
}
            

还有一个更简单的算法，直接看代码

class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;
    }
}

1. https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/
2. https://leetcode.com/articles/best-time-to-buy-and-sell-stock-ii/