贪心 + 前后缀分解 + 动态规划(123. 买卖股票的最佳时机 III)

class Solution {
    //贪心 + 前后缀分解 + 动态规划
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int left[] = new int[n];
        int right[] = new int[n];
        for(int i = 1,Min = prices[0];i < n;i++){
            left[i] = Math.max(left[i - 1],prices[i] - Min);
            Min = Math.min(Min,prices[i]);
        }
        for(int i = n - 2,Max = prices[n - 1]; i >= 0;i--){
            right[i] = Math.max(right[i + 1],Max - prices[i]);
            Max = Math.max(Max,prices[i]);
        }
        int ans = 0;
        for(int i = 0;i < n;i++){
            ans = Math.max(ans,left[i] + right[i]);
        }
        return ans;
    }
}