题目：
思路：
知道要用DP做，但是一开始思路是错的。后来参考了
才意识到可以在整个区间的每一点切开，然后分别计算左子区间和右子区间的最大值，然后再用O(n)时间找到整个区间的最大值。
看来以后碰到与2相关的问题，一定要想想能不能用二分法来做！
下面复制pickless的讲解，我觉得我不能比他讲的更好了
O(n^2)的算法很容易想到：
找寻一个点j，将原来的price[0..n-1]分割为price[0..j]和price[j..n-1]，分别求两段的最大profit。
进行优化：
对于点j+1，求price[0..j+1]的最大profit时，很多工作是重复的，在求price[0..j]的最大profit中已经做过了。
类似于Best Time to Buy and Sell Stock，，可以在O(1)的时间从price[0..j]推出price[0..j+1]的最大profit。
但是如何从price[j..n-1]推出price[j+1..n-1]？反过来思考，我们可以用O(1)的时间由price[j+1..n-1]推出price[j..n-1]。
最终算法：
数组l[i]记录了price[0..i]的最大profit，
数组r[i]记录了price[i..n]的最大profit。
已知l[i]，求l[i+1]是简单的，同样已知r[i]，求r[i-1]也很容易。
最后，我们再用O(n)的时间找出最大的l[i]+r[i]，即为题目所求。
package Level4;import java.util.Arrays;/** * Best Time to Buy and Sell Stock III * * Say you have an array for which the ith element is the price of a given stock on day i.Design an algorithm to find the maximum profit. You may complete at most two transactions.Note:You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again). * */public class S123 {public static void main(String[] args) {//int[] prices = {3,3,5,0,0,3,1,4};int[] prices = {2,1,2,0,1};System.out.println(maxProfit(prices));}// 基本思想是分成两个时间段，然后对于某一天，计算之前的最大值和之后的最大值public static int maxProfit(int[] prices) {if(prices.length == 0){return 0;}int max = 0;// dp数组保存左边和右边的利润最大值int[] left = new int[prices.length];// 计算[0,i]区间的最大值int[] right = new int[prices.length];// 计算[i,len-1]区间的最大值process(prices, left, right);// O(n)找到最大值for(int i=0; i<prices.length; i++){max = Math.max(max, left[i]+right[i]);}return max;}public static void process(int[] prices, int[] left, int[] right){left[0] = 0;int min = prices[0];// 最低买入价// 左边递推公式for(int i=1; i<left.length; i++){left[i] = Math.max(left[i-1], prices[i]-min);// i的最大利润为（i-1的利润）和（当前卖出价和之前买入价之差）的较大那个min = Math.min(min, prices[i]);// 更新最小买入价}right[right.length-1] = 0;int max = prices[right.length-1];// 最高卖出价// 右边递推公式for(int i=right.length-2; i>=0; i–){right[i] = Math.max(right[i+1], max-prices[i]);// i的最大利润为（i+1的利润）和（最高卖出价和当前买入价之差）的较大那个max = Math.max(max, prices[i]);// 更新最高卖出价}//System.out.println(Arrays.toString(left));//System.out.println(Arrays.toString(right));}}
上面的算法中对于天数需要一次扫描，而每次要对交易次数进行递推式求解，所以时间复杂度是O(n*k)，如果是最多进行两次交易，那么复杂度还是O(n)。空间上只需要维护当天数据皆可以，所以是O(k)，当k=2，则是O(1)。
public class Solution {public int maxProfit(int[] prices) {return max(prices, 2);}public int max(int[] prices, int k) {// k: k times transactionsint len = prices.length;if(len == 0) {return 0;}int[][] local = new int[len][k+1];// local[i][j]: max profit till i day, j transactions, where there is transaction happening on i dayint[][] global = new int[len][k+1];// global[i][j]: max profit across i days, j transactionsfor(int i=1; i<len; i++) {int diff = prices[i] – prices[i-1];for(int j=1; j<=k; j++) {local[i][j] = Math.max(global[i-1][j-1]+Math.max(diff,0), local[i-1][j]+diff);global[i][j] = Math.max(global[i-1][j], local[i][j]);}}return global[len-1][k];}}
只有他的好身体，没有地方可去，只想到处流浪、人生就像一场旅行，
