Leetcode 122 Best Time to Buy and Sell Stock II

题目原文

Say you have an array for which the i^th element is the price of a given stock on dayi.
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).

转自：here

题意分析

本题与121题同为买卖问题，不同的是121只能买卖一次，而本题可以买卖多次，但每次买必须在卖过之后。121题采用简单的自底向上动态规划方法解，本题将采用贪心策略。

解法分析

本题是一个最优化问题，采用动态规划方法有点杀鸡焉用宰牛刀，本题我采用贪心策略。使用贪心策略要考虑两点，一是贪心选择，二是最优子结构。首先看贪心选择，这里贪心选择为一次贪心买卖。对于买入的时机，如果下一天的值更小，则选择下一天买，这样肯定能比在前一天买获得更多收益，如果后一天的值大于前一天买入值了，则开始考虑是否卖出，遍历剩下的天数，直到数值开始下降，在下降的前一天卖出，这样一次贪心的买卖完成，剩下的天数为子问题，具有最优子结构。C++代码如下：

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int i;
        auto n=prices.size();
        if(n==0||n==1)
            return 0;
        int maxPro=0;
        int buy=prices[0],sell;
        for(i=0;i<n;i++){
            buy=prices[i];
            if(prices[i+1]<=buy)
                buy=prices[i+1];  
            else{
                while((prices[i]<=prices[i+1])&&(i+1)<n)
                    i++;
                sell=prices[i];
                maxPro+=(sell-buy);
            }   
        }
        return maxPro;      
    }
};

算法复杂度为O(n)，用buy和sell来保存每次买卖的价格。