[Leetcode] 123. Best Time to Buy and Sell Stock III

比眉伴天荒 2022-06-14 00:07 115阅读 0赞

# 123. Best Time to Buy and Sell Stock III #

Say you have an array for which the i-th 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(ie, you must sell the stock before you buy again).

**给定一个数组，表示股票第i天的价格，怎么进行股票交易才能获得最大的利润。只能进行2次股票买卖。**

**解题思路**  
这道题的困难程度是标记为Hard的题目。本题与之前两道题目**\[121\]\[122\]**的区别在于，**\[121\]**限制了股票交易的次数只能是一次， **\[122\]**则不对股票交易的次数做限制。这两种交易规则都相对比较简单，而本题限制股票交易次数是2次。提升了本题的难度。

这里，我采用了动态规划的思想。  
设状态f(i)，表示区间\[0, i\](0 <= i <= n-1)的最大利润。  
设状态g(i)，表示区间\[i, n-1\](0 <= i <= n-1)的最大利润。  
则最终能够获得最大利润为max = \{f(i) + g(i)\}, 0 <= i <= n-1。  
题目限制了股票交易的次数是两次。但是我们也可以在同一天内买进和卖出，也就相当于不交易。

代码实现如下：

class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            if(prices.size() < 2)
                return 0;
            const int n = prices.size();
            vector<int> f(n,0);
            vector<int> g(n,0);
            for(int i = 1, valley = prices[0]; i < n; i++)
            {
                valley = min(valley, prices[i]);
                f[i] = max(f[i-1], prices[i]-valley);
            }
    
            for(int i = n-2, peak = prices[n-1]; i >= 0; i--)
            {
                peak = max(peak, prices[i]);
                g[i] = max(g[i], peak-prices[i]);
            }
    
            int max_profit = 0;
            for(int i = 0; i < n; i++)
            {
                max_profit = max(max_profit,f[i]+g[i]);
            }
            return max_profit;
        }
    };

本题也可以看做是最大m字段和，本题取m=2。