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; } }