题目

法1：单次遍历，Best!

class Solution {public int maxProfit(int[] prices) {int f1 = -prices[0], f2 = 0, f3 = -prices[0], f4 = 0;for (int i = 1; i < prices.length; ++i) {f1 = Math.max(f1, -prices[i]);f2 = Math.max(f2, f1 + prices[i]);f3 = Math.max(f3, f2 - prices[i]);f4 = Math.max(f4, f3 + prices[i]);}return f4;}
}

法2：基于单次买卖+3次遍历

class Solution {public int maxProfit(int[] prices) {int max = 0, n = prices.length;int[] dp1 = new int[n]; // dp[i]从0~i天内的最大收益int[] dp2 = new int[n]; // dp[i]从i~n-1天内的最大收益int minCost = prices[0], maxPrice = prices[n - 1], ans = 0;for (int i = 1; i < n; ++i) {minCost = Math.min(minCost, prices[i]);dp1[i] = Math.max(dp1[i - 1], prices[i] - minCost);}for (int i = n - 2; i >= 0; --i) {maxPrice = Math.max(maxPrice, prices[i]);dp2[i] = Math.max(dp2[i + 1], maxPrice - prices[i]);}for (int i = 0; i < n; ++i) {ans = Math.max(ans, dp1[i] + dp2[i]);}return ans;}
}