前后缀分解

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

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

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

class Solution {
public:int maxProfit(vector& prices) {int n = prices.size();vector 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. 时间复杂度 : O(n)O(n)O(n) ， 维护前缀和，维护后缀和的同时求答案的时间复杂度 O(n)O(n)O(n) 。
2. 空间复杂度 : O(n)O(n)O(n) ， 前缀和数组的空间复杂度 O(n)O(n)O(n) 。

AC