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

男娘i 2022-05-06 10:50 278阅读 0赞

*  1.  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;
            }
        }
    };