题目描述

给你一个数组，第 $i$ 个元素表示第 $i$ 天股票的价格。
你最多可以交易两次。
请设计一个算法，求最大收益。

注意：必须先买再卖，且每天只能买或者卖一次。

样例1

输入：[3,3,5,0,0,3,1,4]
输出：6
解释：一共交易两次：
第4天买（价格是0），第6天卖（价格是3），收益3；
第7天卖（价格是1），第8天卖（价格是4），收益3；
总共收益6。

样例2

输入：[1,2,3,4,5]
输出：4
解释：一共交易一次：
第1天买（价格是1），第5天卖（价格是5），收益4。
注意不能第1天买第3天卖，然后第3天买第5天卖，因为
每天只能进行买或者卖一种操作。

样例3

输入：[7,6,4,3,1]
输出：0
解释：不做任何交易，收益0。

算法

(线性扫描) $O(n)$

先从前往后扫描，并计算出只买卖一次且第 $i$ 天卖出的最大收益，最大收益等于第 $i$ 天股票的价格减去前 $i-1$ 天股票价格的最小值。
扫描过程中用 $f[i]$ 记录前 $i$ 天中买卖一次的最大收益（不一定在第 $i$ 天卖）。

然后枚举第二次交易，从后往前扫描，并计算只买卖一次且第 $i$ 天买入的最大收益，最大收益等于第 $i$ 天之后股票价格的最大值减去 第 $i$ 天的价格，然后加上 $f[i-1]$，就是第二次交易在 $i$ 天买入，两次交易的总收益的最大值。
枚举过程中维护总收益的最大值即可。

时间复杂度分析：整个数组总共扫描两遍，所以时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        if (!n) return 0;
        vector<int> f(n, 0);
        int minv = INT_MAX;
        for (int i = 0; i < n; i ++ )
        {
            if (i) f[i] = f[i - 1];
            if (prices[i] > minv)
                f[i] = max(f[i], prices[i] - minv);
            minv = min(minv, prices[i]);
        }
        int res = f[n - 1];
        int maxv = INT_MIN;
        for (int i = n - 1; i > 0; i -- )
        {
            if (prices[i] < maxv)
                res = max(res, maxv - prices[i] + f[i - 1]);
            maxv = max(maxv, prices[i]);
        }
        return res;
    }
};