?

題解：?

根據題目要求，最多進行兩次買賣股票，而且手中不能有2只股票，就是不能連續兩次買入操作。

所以，兩次交易必須是分布在2各區間內，也就是動作為：買入賣出，買入賣出。

進而，我們可以劃分為2個區間[0,i]和[i,len-1]，i可以取0~len-1。

那么兩次買賣的最大利潤為：在兩個區間的最大利益和的最大利潤。

一次劃分的最大利益為：Profit[i] = MaxProfit(區間[0,i]) + MaxProfit(區間[i,len-1]);

最終的最大利潤為：MaxProfit(Profit[0], Profit[1], Profit[2], ... , Profit[len-1])。\

參考：http://www.cnblogs.com/springfor/p/3877068.html

?

public class Solution {public int maxProfit(int[] prices) {if (prices == null || prices.length <= 1) {return 0;}int[] left = new int[prices.length];int[] right = new int[prices.length];
//DP from left to rightint min = prices[0];for (int i = 1; i < prices.length; i++) {min = prices[i] < min ? prices[i] : min;left[i] = Math.max(left[i - 1], prices[i] - min);}
//DP from right to leftint max = prices[prices.length - 1];for (int i = prices.length - 2; i >= 0; i--) {max = prices[i] > max ? prices[i] : max;right[i] = Math.max(max - prices[i], right[i+1]);}int profit = 0;for (int i = 0; i < prices.length; i++) {profit = Math.max(left[i] + right[i], profit);}return profit;} }

?

轉載于:https://www.cnblogs.com/77rousongpai/p/4521403.html

總結

以上是生活随笔為你收集整理的123 Best time to buy and sell stock iii的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。