力扣(LeetCode)123. 买卖股票的最佳时机 III(C++)

前后缀分解

维护前缀和数组，保存 $1$~$i$ 天，买卖一次的最大利润。维护后缀和数组，保存 $i$~$n$ 天买卖一次的最大利润。枚举所有分界点 $i$ ，买卖两次的最大利润 $=i$ 的前缀和 $+i$ 的后缀和 $=1$~$i$ 天买卖一次的最大利润 $+i$~$n$ 天买卖一次的最大利润。

由于用到前缀和，所有下标后移一位。前缀和数组 $0$ 的位置置 $0$ ，表示第 $0$ 天没有交易利润是 $0$ 。

后缀和数组从后往前维护，可以参照 $121$ 题，用一个变量表示。维护后缀和，可以同时加上前缀和，这样可以省一次遍历，直接算出答案。

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n = prices.size();
        vector<int> f(n+1);
        for(int i = 1,minp = INT_MAX;i<=n;i++){
            minp = min(minp,prices[i-1]);
            f[i] = max(f[i-1],prices[i-1]-minp);
        }
        int ans = 0;
        for(int i = n,maxp = 0;i;i--){
            maxp = max(maxp,prices[i-1]);
            ans = max(ans,maxp-prices[i-1]+f[i-1]);
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

1. 时间复杂度 : $O(n)$ ， 维护前缀和，维护后缀和的同时求答案的时间复杂度 $O(n)$ 。
2. 空间复杂度 : $O(n)$ ， 前缀和数组的空间复杂度 $O(n)$ 。

AC