LeetCoder - Best Time to Buy and Sell Stock III

Say you have an array for which the i^th 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 Solution {
    public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(prices==null || prices.length<2) {
            return 0;
        }
        int maxGap = 0;
        int min = 0;
     
        int left[] = new int[prices.length];
        int right[] = new int[prices.length+1];
        right[prices.length] = 0;
     
        left[0] = 0;
        min = prices[0];
        for(int i=1;i<prices.length;i++) {
            maxGap = Math.max(maxGap, prices[i]-min);
            min = Math.min(min, prices[i]);
            left[i] = maxGap;
        }
     
        maxGap = 0;
        int max = prices[prices.length-1];
        for(int i=prices.length-2;i>=0;i--) {
            maxGap = Math.max(maxGap, max - prices[i]);
            max = Math.max(max, prices[i]);
            right[i] = maxGap;
        }
     
        int overallMax = 0;
        for(int i=0;i<prices.length;i++) {
            int overall = left[i] + right[i+1];
            overallMax = Math.max(overallMax, overall);
        }
        return overallMax;
    }
}

==============

public class Solution { public int maxProfit(int[] prices) { int hold1 = Integer.MIN_VALUE, hold2 = Integer.MIN_VALUE; int release1 = 0, release2 = 0; for(int i:prices){ // Assume we only have 0 money at first release2 = Math.max(release2, hold2+i); // The maximum if we've just sold 2nd stock so far. hold2 = Math.max(hold2, release1-i); // The maximum if we've just buy 2nd stock so far. release1 = Math.max(release1, hold1+i); // The maximum if we've just sold 1nd stock so far. hold1 = Math.max(hold1, -i); // The maximum if we've just buy 1st stock so far. } return release2; ///Since release1 is initiated as 0, so release2 will always higher than release1. } }