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

Solution 1: Use 2 DP arrays, dp1[i] is max profit of [0...i] and dp2[i] is max profit of [i..n-1], then it is convert to one transaction problem.

 public class Solution {  
   public int maxProfit(int[] prices) {  
     int n=prices.length;  
     int[] dp1=new int[n];  
     int[] dp2=new int[n];  
     int profit=0;  
     for (int i=0; i<n; i++) {  
       if (i==0) {  
         profit=0;  
         dp1[i]=0;  
       }  
       else {  
         profit=Math.max(0,profit+prices[i]-prices[i-1]);  
         dp1[i]=Math.max(dp1[i-1],profit);  
       }  
     }  
     for (int i=n-1; i>=0; i--) {  
       if (i==n-1) {  
         profit=0;  
         dp2[i]=0;  
       }  
       else {  
         profit=Math.max(0,profit+prices[i+1]-prices[i]);  
         dp2[i]=Math.max(dp2[i+1],profit);  
       }  
     }  
     int res=0;  
     for (int i=0; i<n; i++) res=Math.max(res,dp1[i]+dp2[i]);  
     return res;  
   }  
 }