class Solution {
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[] p1 = new int[n];  //p[0][i]
        int[] p2 = new int[n];  //p[i][n-1]

        int maxValue = 0;
        //dp[i]用来表示前i天股市的最低价格
        int dp = Integer.MAX_VALUE;
        for(int j=0; j!=n; j++){
            maxValue = Math.max(maxValue,prices[j]-dp);
            p1[j] = maxValue;
            dp = Math.min(dp,prices[j]);
        }

        int minValue = 0;
        //dp[i]用来表示前i天股市的最高价格
        dp = 0;
        for(int j=0; j!=n; j++){
            minValue = Math.min(minValue,prices[n-1-j]-dp);
            p2[n-1-j] = -minValue;
            dp = Math.max(dp,prices[n-1-j]);
        }

        int max_profit = 0;
        for(int i=0; i!=prices.length; i++){
            max_profit = Math.max(max_profit,p1[i]+p2[i]);
        }
        return max_profit;

    }
}