[Java Solution] DP- seperate to left[i]&right[i], easy to understand.


  • 0
    public class Solution {
    public int maxProfit(int[] prices) {
        //at most two transactions means we can seperate the problem to left array & right array
        if(prices.length<2) return 0;
        int[] left=new int[prices.length];
        int[] right=new int[prices.length];
        //left side is the same as "Best Time to Buy and Sell Stock"
        int minPrice=prices[0];
        for(int i=1;i<prices.length;i++){
            if(prices[i]>=minPrice){
                left[i]=Math.max(left[i-1],prices[i]-minPrice);
            }
            else{
                left[i]=left[i-1];
                minPrice=prices[i];
            }
        }
        //right side starts from the end of array.
        int maxPrice=prices[prices.length-1];
        for(int i=prices.length-2;i>=0;i--){
            if(prices[i]<maxPrice){
                right[i]=Math.max(maxPrice-prices[i],right[i+1]);
            }
            else{
                right[i]=right[i+1];
                maxPrice=prices[i];
            }
        }
        //get the max of left[i]+right[i];
        int max=0;
        for(int i=0;i<prices.length;i++){
            max=Math.max(max,left[i]+right[i]);
        }
        return max;
    }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.