学步园

这三道题目思路相近，可以看成都是通过动态规划实现，不过 II 其实应该算是贪心，只要能够赚钱就进行交易，而 I 和 III 对交易次数进行了限制，后者可以看成是前者的推广，通过对前者使用二分的方法，将一个数组看成两个按前者的方法求解即可。I 的求解方法是通过记录前面的最小值，并不断判断差价，最终找到最大差价的

Best Time to Buy and Sell Stock I    

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if(prices.size()<=1)return 0;
        int result=0;
        int begin=prices[0],end=prices[0];
        for(int i=1;i<prices.size();i++){
            if(prices[i]-begin>result)
                result=prices[i]-begin;
            if(begin>prices[i])begin=prices[i];
        }
        return result;
    }
};

Best Time to Buy and Sell Stock  II 

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int sum=0;
        for(int i=prices.size()-1;i>0;i--){//tanxin
            prices[i]-=prices[i-1];
            if(prices[i]>0)sum+=prices[i];
            
        }
        return sum;
             
        
    }
};

Best Time to Buy and Sell Stock  III 

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        int ans=0;
        if(prices.size()<=1)return 0;
        int tres=0;
        int len=prices.size();
        int maxl[len],maxr[len];
        memset(maxl,0,sizeof(maxl));
        memset(maxr,0,sizeof(maxr));
        int begin=prices[0];
        for(int i=1;i<len;i++){
              if(begin>prices[i])begin=prices[i];
              if(prices[i]-begin>ans)ans=prices[i]-begin;
              maxl[i]=ans;
        }
        ans=0;
        begin=prices[len-1];
        for(int i=len-2;i>=0;i--){
                 if(begin-prices[i]>ans)
                     ans=begin-prices[i];
                 if(begin<prices[i])begin=prices[i];
                 maxr[i]=ans;
        }
        for(int i=1;i<len;i++){
             if(ans<maxl[i-1]+maxr[i])
             ans=maxl[i]+maxr[i];
        }
        return ans;
        
    }
};