leetcode 121 122 123 . Best Time to Buy and Sell Stock

121题目描述：

解题:记录浏览过的天中最低的价格，并不断更新可能的最大收益，只允许买卖一次的动态规划思想。

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

122 可以重复的进行买入卖出，但是卖出时间必须在买入时间之后

思路：划分最小的时间粒度进行买卖，即相邻两天，相邻两天只要买入卖出有收益则进行买卖，否则不进行买卖　

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

123 最多进行两次买卖后的最大收益

以第i天对n个时间进行划分两半分别计算两部分的最大收益再进行加和但是时间复杂度为 O(n²) 超时！！！！

public class Solution {
    public int maxProfit(int[] prices) {
        int ans = 0;
        for(int m = 0; m<prices.length; m++){
            int tmp = maxProfitOnce(prices, 0, m) + maxProfitOnce(prices, m, prices.length-1);
            if(tmp > ans) ans = tmp;
        }
        return ans;
    }

    public int maxProfitOnce(int[] prices,int start, int end){
        if(start >= end) return 0;
        int low = prices[start];
        int ans = 0;
        for(int i=start+1; i<=end; i++){
            if(prices[i] < low) low = prices[start];
            else if(prices[i] - low > ans) ans = prices[i] - low;
        }
        return ans;
    }

}

　利用网上动态规划的思想来做

　　我们定义local[i][j]为在到达第i天时最多可进行j次交易并且最后一次交易在最后一天卖出的最大利润，此为局部最优。然后我们定义global[i][j]为在到达第i天时最多可进行j次交易的最大利润，此为全局最优。它们的递推式为：维护了两个递推变量

　　　　local[i][j]=max(global[i-1][j-1]+max(diff,0),local[i-1][j]+diff) 局部最优中的local[i-1][j] + diff 可以看为在第i-1天卖出后又买入在第i天又卖出的操作，所有和总的买卖次数还是j次，所以diff无论正负都得加入。

　　　　global[i][j]=max(local[i][j],global[i-1][j])，

　　其中局部最优值是比较前一天并少交易一次的全局最优加上大于0的差值，和前一天的局部最优加上差值中取较大值，而全局最优比较局部最优和前一天的全局最优。

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        if (prices.empty()) return 0;
        int n = prices.size(), g[n][3] = {0}, l[n][3] = {0};
        for (int i = 1; i < prices.size(); ++i) {
            int diff = prices[i] - prices[i - 1];
            for (int j = 1; j <= 2; ++j) {
                l[i][j] = max(g[i - 1][j - 1] + max(diff, 0), l[i - 1][j] + diff);
                g[i][j] = max(l[i][j], g[i - 1][j]);
            }
        }
        return g[n - 1][2];
    }
};