123-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).

思路：

1.交易两次与交易一次的做法类似，只需将数组拆分成两个数组，然后分别求两个数组交易一次的最大值，再相加；

2.假设数组在索引i处拆分，将0-i之间的数组元素的最大值放入list1中，将i-n之间的数组元素的最大值放入list2中

3.遍历i,判断取i何值时，获得最大收益

【算法实现】

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices==null||prices.length<=0)
            return 0;
        int len=prices.length;                       //数组长度
        List<Integer> dp_pre=new ArrayList<Integer>();         //0-i的子数组
        List<Integer> dp_post=new ArrayList<Integer>();       //i-n的字数组
        
        int min_pre=Integer.MAX_VALUE;
        int max_pre=0;
        for(int i=0;i<len;i++) {
            if(prices[i]<min_pre)
                min_pre=prices[i];
            if(prices[i]-min_pre>max_pre)
                max_pre=prices[i]-min_pre;
            dp_pre.add(max_pre);
        }                                                                                 //填充dp_pre
        
        int max_post=prices[len-1];
        int max_pro=0;
        for(int i=len-1;i>=0;i--) {
            if(prices[i]>max_post)
                max_post=prices[i];
            if(max_post-prices[i]>max_pro)
                max_pro=max_post-prices[i];
            dp2.add(max_pro);
        }                                                                              //填充dp_post
        
        int max=0;
        for(int i=1;i<len;i++) {
            if(dp1.get(i)+dp2.get(len-1-i)>max)
                max=dp1.get(i)+dp2.get(len-1-i);
        }
        
        return max; 
    }
}

v2版本---思路相同，相对简洁
public class Solution {
    public int maxProfit(int[] prices) {
        if(len<=0)
            return 0;
        int maxPro1=0;
        int min1=prices[0];
        List<Integer> mp=new ArrayList<Integer>();
        mp.add(maxPro1);
        for(int i=1;i<len;i++) {
            if(prices[i]-min1>maxPro1)
                maxPro1=prices[i]-min1;
            if(prices[i]<min1) 
                min1=prices[i];
            mp.add(maxPro1);
        }
        int maxPro2=0;
        int max2=prices[len-1];
        for(int i=len-2;i>=0;i--) {
            if(max2-prices[i]+mp.get(i)>maxPro2) {
                maxPro2=max2-prices[i]+mp.get(i);
            }
            if(prices[i]>max2)
                max2=prices[i];
        }
        return maxPro2;     
    }
}