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

Solution 1: DP, $O(n)$ time and $O(n)$ space.

public class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length==0) return 0;
        
        int min = prices[0];
        int[] preProfit = new int[prices.length];
        for(int i=1; i<prices.length; i++){
            min = Math.min(min, prices[i]);
            preProfit[i] = Math.max(preProfit[i-1], prices[i]-min);
        }
        
        int max = prices[prices.length-1];
        int[] posProfit = new int[prices.length];
        for(int i=prices.length-2; i>=0; i--){
            max = Math.max(max, prices[i]);
            posProfit[i] = Math.max(posProfit[i+1], max-prices[i]);
        }
        
        int maxProfit = 0;
        for(int i=0; i<prices.length; i++) 
            maxProfit=Math.max(maxProfit, preProfit[i]+posProfit[i]);
        
        return maxProfit;
    }
}

Solution 2: DP, $O(n)$ time and $O(1)$ space.

public class Solution {
    public int maxProfit(int[] prices) {
        
        int min1 = Integer.MAX_VALUE;
        int prf1 = 0;
        int min2 = Integer.MAX_VALUE;
        int prf2 = 0;
        
        for(int p : prices){
            min1 = Math.min(min1, p);
            prf1 = Math.max(prf1, p-min1);
            min2 = Math.min(min2, p-prf1);
            prf2 = Math.max(prf2, p-min2);
        }
        
        return prf2;
    }
}