股票买卖最大收益总结-Best Time to Buy and Sell Stock

• 123. 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 at most two transactions.
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).

分析题目的意思就是说可以买卖一次或者两次甚至不买卖，求出最大化的收益。
如果只买卖一次那么问题就变成另一个问题：只买卖一次能够获得的最大收益。这个问题采用动归的递推形式就能够解决。而买卖两次的情况是可以化成买卖1次的最大值问题。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if(n<=1) return 0;
        
        vector<int> f(n,0),g(n,0);
        int temp = INT_MAX,cur_max = 0;
        //f[i]为前i个股票最多只买卖一次能够获得最大收益
        for(int i=0;i<n;++i) {
            temp = min(temp,prices[i]);
            f[i] = max(cur_max,prices[i]-temp);
            cur_max = f[i];
        }
        temp = 0;
        cur_max = 0;
        //g[i]为后n-i个股票最多只买卖一次能够获得的最大收益
        for(int i=n-1;i>=0;--i) {
            temp = max(temp,prices[i]);
            g[i] = max(cur_max,temp - prices[i]);
            cur_max = g[i];
        }
        //总的收益是所有可能选择的2分段的最大值
        int res = 0;
        for(int i=0;i<n;++i) {
            res = max(res,g[i]+f[i]);
        }
        return res;
    }
};

这不是一道典型的动归，但是也是使用了动态规划的思想。
首先很容易想到将问题拆分成两段，每一段对应一个只用最多一次交易获取的最大值。这样只需要将两段加起来就是整体的最大值。对于划分成两段的划分方法有n种，所以只需要遍历这n种划分选择，求最大值即可。
下面就是怎么求一段序列prices[0:i]当中只最多买卖一次可以获得的最大值。这个问题稍微思考一下就知道，只需要遍历整个序列，每次更新一个最小值变量temp保存当前遇到的最小值，那么当前可以获得的最大收益为
g[i] = max(prices[k] - temp, g[i-1])
当前的最优解只和前一个阶段的最优解有关，这不就是DP的最优子结构么~，由于当前最优解只和前一个阶段的最优解有关，不需要做出选择，所以就是简单的递推形式。如果从自顶向下的形式去分析就不行了，因为
dp(i) = max(dp(i-1), prices[i] - m[i-1]) ，m[i-1]为0…i-1区间的最小值。
m[i] = min(prices[i], m[i-1])
也就是说自顶向下还得开一个数组去记录每一个阶段的最小值:
写出来的形式就是：

def dp(i,prices,m):
	if i == 0:
		m[i] = prices[0]
		return 0
		
	 cur = max(dp(i-1,prices,m),prices[i] - m[i-1])
	 m[i] = min(prices[i], m[i-1]) 
	 return cur

所以这样的问题还是自底向上写比较的顺手，但是就是容易忽视其DP的本质。

做这样的题目还是不能先上来当做直接的dp去做，需要先从题目本身上对题目进行相应的抽象，转化成容易解决的子问题，对问题进行转化，再对抽象的问题进行模型的匹配求解。一个问题必然需要考察某一个知识点，所以扒开问题的外衣找到真实的考点是关键的第一步。然后才是分析问题采用最合适的算法去解决。

class Solution {
public:
    int maxProfit(vector<int> &prices) {
        // f[k, ii] represents the max profit up until prices[ii] (Note: NOT ending with prices[ii]) using at most k transactions. 
        // f[k, ii] = max(f[k, ii-1], prices[ii] - prices[jj] + f[k-1, jj]) { jj in range of [0, ii-1] }
        // = max(f[k, ii-1], prices[ii] + max(f[k-1, jj] - prices[jj]))
        // f[0, ii] = 0; 0 times transation makes 0 profit
        // f[k, 0] = 0; if there is only one price data point you can't make any money no matter how many times you can trade
        if (prices.size() <= 1) return 0;
        else {
            int K = 2; // number of max transation allowed
            int maxProf = 0;
            vector<vector<int>> f(K+1, vector<int>(prices.size(), 0));
            for (int kk = 1; kk <= K; kk++) {
                int tmpMax = f[kk-1][0] - prices[0];
                for (int ii = 1; ii < prices.size(); ii++) {
                    f[kk][ii] = max(f[kk][ii-1], prices[ii] + tmpMax);
                    tmpMax = max(tmpMax, f[kk-1][ii] - prices[ii]);
                    maxProf = max(f[kk][ii], maxProf);
                }
            }
            return maxProf;
        }
    }
};