C++练习：股票买卖的最佳时机(1~4)

121. 买卖股票的最佳时机

简介

这是一道简单题，思路是找卖出那一天前的最低价格，然后记录卖出后的最大利润。按照动态规划的思路解题，我们需要找到原问题和子问题的转移关系。

分析：n天内的最大利润，一定是1~n内某一天卖出股票的最大利润。我们知道要使我们手中的股票得到最大利润，就要在之前的最低价格购买。所以我们只要建立一个最低价格数组minimon，记录第i天前的最低价格，我们就可以得到第i天卖出股票的最大利润prices[i] - minimon[i]。

而如何维护minimon数组？显然minimon[i]肯定是minimon[i-1]（之前的最低价）和prices[i]（第i天的价格）二者之一。故我们得到状态转移方程minimon[i] = min(minimon[i-1],prices[i]）；

因为维护最低价格数组和计算当天最大利润和记录最大利润可以一起进行，所以只需要一次遍历就能的到答案。

代码

int maxProfit(vector<int>& prices) {
        int ans = 0, n = prices.size();
        vector<int> dp(n, 0);
        dp[0] = prices[0];
        for(int i = 1; i < n; ++ i){
            dp[i] = min(dp[i-1], prices[i]);
            int profit = prices[i] - dp[i];
            ans = max(ans, profit);
        }
        return ans;
    }

优化

观察到在计算profit时只会用到最新的一个最低价，故可以用一个数来记录最新的最低价，而免去使用数组。且更改最低价和记录最大利润不会同时进行（同一天买卖的利润为0）。

代码

int maxProfit(vector<int>& prices) {
        int ans = 0, low = prices[0];
        for(int i = 1; i < prices.size(); ++ i){
            if(prices[i] < low){
                low = prices[i];
            }
            else{
                ans = max(ans, prices[i] - low);
            }
        }
        return ans;
    }

评价

比起动态规划，我觉得这题更像是贪心。只要找到最大的正向落差就可以了。

122. 买卖股票的最佳时机 II

简介

这题是非常简单的贪心问题。我们只需要记录每一天的纯利润的累计，就可以得到答案了。即只要今天的价格比前一天高我们就把这个高出的部分加入答案。相当于我们每天都买入股票，然后到第二天选择高价卖出或原价卖出，稳赚不赔啊。

代码

int maxProfit(vector<int>& prices) {
        int ans = 0, price = prices[0];
        for(int i = 0; i < prices.size(); ++ i){
            if(prices[i] > price){
                ans += prices[i] - price;
            }
            price = prices[i];
        }
        return ans;
    }

123. 买卖股票的最佳时机 III

方法一

这一题与第一题没有本质的区别，只是多了一次交易次数。相信在有了第一题的基础上，我们能很快得到一种解法。这里先给出代码，相信大家一眼就能看出。

int maxProfit(vector<int>& prices) {
        int ans = 0;
        int n = prices.size();
        vector<int> dp(n, 0);
        int lowPri = prices[0];
        for(int i = 1; i < n; ++ i){
            if(prices[i] < lowPri) lowPri = prices[i];
            else{
                dp[i] = prices[i] - lowPri;
                ans = max(ans, dp[i]);
            }
        } // 0~i的最大利润
        if(n < 4) return ans;
        int highPri = prices[n-1], maxPro = 0;
        for(int i = n-2; i > 0;  -- i){
            if(prices[i] > highPri){
                highPri = prices[i];
            }
            else{
                dp[i] = highPri - prices[i];
                maxPro = max(maxPro, dp[i]);
            }
            ans = max(ans, dp[i-1]+maxPro);
        } // i~n的最大利润
        return ans;
    }

思路很简单，我们只要把数组分成两部分分别计算每部分的最大利润，不同的划分方法有不同的总利润，通过比较每一种划分的总利润我们就可以得到答案。代码里做了一些优化，在有了dp[i]前部分的最大利润之后，我们只需要知道后半部分i+1~n的最大利润就能得到总利润了。通过反向计算，我们可以用和第一题同样的方法计算后半部分i+1~n的最大利润。

方法二

当然这个求序列划分的题目我们可以用动态规划来解决。让我们先来确定一个原始问题，我们把进行两次交易后账户的金额作为我们的原问题（只进行一次交易或不进行交易的情况可以视为在同一天买进卖出，这样利润为0不会对结果产生影响），我们要求原问题的最大值。现在我们要找状态转移关系。第二次交易后的总利润，应该是第一次交易利润加上的二次交易的利润。而一次买卖有分成低价买入，高价卖出两部分。所以我们的账户的金额是这样变化的：

amount0(初始资金，设为0)--->amount0 - prices[i](第一次买入,记为amount1) --->amount1+prices[j](第一次卖出,记为amount2)--->amount2-prices[k](第二次买入，记为amount3)--->amount3+prices[l](最终利润，记为amount4)

因为amount0=0，可以忽略。所以我们可以由四个状态推出原问题。而每个状态的我们可以找出它的子问题。比如对于amount1[i]它是第一次买入时的花费price的相反数，通过第一题我们知道price代表第i天前的最低价格。所以amount1[i] = max(amount1[i-1], prices[i])。同第一题最大利润amount2[i] = max(amount2[i-1], prices[i] + amount1[i]),后面的一项指把手中的股票卖出后的账户金额。

而对应amount3它指的是第一次交易完成后再购买股票后的账户金额。当j==k时，即同一天卖出买入，没有利润，相当于只进行了一次交易。amount3[i] = max(amount3[i-1], amount2[i] - prices[i])。

相信看到这里我们可以很容易的到amount4[i] = max(amount4[i-1], amount3[i] - prices[i])。

代码：

int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(n, vector<int>(4, 0));
        dp[0][0] = -prices[0], dp[0][2] = -prices[0];

        for(int i = 1; i < n; ++i){
            dp[i][0] = max(dp[i-1][0], -prices[i]);
            dp[i][1] = max(dp[i-1][1], dp[i][0] + prices[i]);
            dp[i][2] = max(dp[i-1][2], dp[i][1] - prices[i]);
            dp[i][3] = max(dp[i-1][3], dp[i][2] + prices[i]);
        }

        return dp[n-1][3];
    }

优化

观察到数组的每一列之和前一列和当前列有关，可以用滚动数组优化，做法也和第一题类似

int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<vector<int>> dp(2, vector<int>(2, 0));
        dp[0][0] = -prices[0], dp[1][0] = -prices[0];

        for(int i = 1; i < n; ++i){
            dp[0][0] = max(dp[0][0], -prices[i]);
            dp[0][1] = max(dp[0][1], dp[0][0] + prices[i]);
            dp[1][0] = max(dp[1][0], dp[0][1] - prices[i]);
            dp[1][1] = max(dp[1][1], dp[1][0] + prices[i]);
        }

        return dp[1][1];
    }

记住这个格式，下一题会用到

188. 买卖股票的最佳时机 IV

孰能生巧，相信做到这里。大家对于这类题目不说一眼秒杀，也能信手捏来。

这里就直接给代码了

int maxProfit(int k, vector<int>& prices) {
        vector<vector<int>> fund(k, vector<int>(2, 0)); // 账户资金
        for(int i = 0; i < k; ++ i) // 第笔交易买入后的资金
            fund[i][0] = -prices[0];
        for(int i = 1; i < prices.size(); ++ i){
            fund[0][0] = max(fund[0][0], -prices[i]);
            fund[0][1] = max(fund[0][1], prices[i] + fund[0][0]);
            for(int j = 1; j < k; ++ j){
                // 第i笔交易买入后的资金是第i-1笔交易卖出后的资金减去买股票的钱
                fund[j][0] = max(fund[j][0], fund[j-1][1] - prices[i]);
                // 第i笔交易卖出后的资金，即前i笔交易的最大总利润
                fund[j][1] = max(fund[j][1], prices[i] + fund[j][0]);
            }   
        }
        return fund[k-1][1];  // 返回最大总利润
    }

总结

对于这类的动态规划题目，我们只要找到子问题和原问题之间的状态转移关系，就已经解决80%的问题了。当然这也是题目的难点。还有一个要注意的地方就是，我们要求的问题可能不是可以直接动态规划的，这时我们就要找到一个与题目问题相关又能分解成子问题的原问题。就像第三题，我们把求不超过两次交易的最大利润，转化为求两次交易后的最大账户资金。就像把求最长子序列，转化为求包含第i个元素的最长序列。总之我们要把握住动态规划的五步，1.找到原问题，2.分解子问题，3.确定初始条件，4.状态转移，5.判断边界条件。

因为动态规划需要存储子问题的状态，所以也经常会用到状态压缩。就像本文用到的滚动数组。