题目描述

假设你有一个数组，其中第i个元素表示第i天某个股票的价格。

设计一种算法以找到最大利润，可以完成最多两次交易（一买一卖算一次交易），但必须先购买股票再出售股票，不能同时多次交易。

样例

Example 1:

输入: [3,3,5,0,0,3,1,4]
输出: 7
解释: 第四天买(price = 0)，第六天卖(price=3)，利润为3；
第七天买(price = 1)，第八天卖(price=4)，利润为3。

Example 2:

输入: [1,2,3,4,5]
输出: 4
解释: 第一天买(price = 1)，第五天卖(price=5)，利润为4。

Example 3:

输入: [7,6,4,3,1]
输出: 0
解释: 这个例子中没有完成交易。

算法1 动态规划

Time $O(n)$, Space $O(n)$

在整个区间的每一点切开， 然后分别计算左子区间和右子区间的最大值，然后再用O(n)时间找到整个区间的最大值。

1. 遍历一遍数组，求$[0,i-1]$区间的最大利润$f(i)$，具体做法是找当前最低价格low，判断是要以low买入当天卖出，还是不动
2. 从后往前遍历，求$[i,n-1]$区间的最大利润$g(i)$，具体做法是找当前最高价格high，判断是要当天买入以high卖出，还是不动
3. 遍历，求最大利润$max(f(i)+g(i))$

复杂度分析：每次遍历数组都是$O(n)$时间，所以三次还是$O(n)$；两个新数组$f(i)，g(i)$都是额外占用$O(n)$空间。

C++ 代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size(), result = 0;
        if(n < 2) return 0;
        vector<int> f(n,0), g(n,0);

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

        for(int i = n-2, high = prices[n-1]; i >= 0; --i){
            high = max(high, prices[i]);
            g[i] = max(g[i+1], high - prices[i]);
        }

        for(int i = 0; i < n; ++i){
            result = max(result, f[i] + g[i]);
        }
        return result;
    }
};