Say you have an array for which the ith element is the price of a given stock on day i.

maxProfit.java

/*
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).
*/
public class Solution {
    public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int size = prices.length;
        int max = 0;
        
        if(size == 1) return 0;
        
        for(int i = -1; i < size; i++) {
            int left = getPrice(prices, 0, i+1);
            int right = getPrice(prices, i+1, size);
            int cur = left + right;
            if(cur > max) {
                max = cur;
            }
        }
        
        return max;
    }
    
    public int getPrice(int[] prices, int start, int end) {
        int min = Integer.MAX_VALUE;
        int diff = 0;
        int max = 0;
        for(int i = start; i < end; i++) {
            min = Math.min(min, prices[i]);
            max = Math.max(max, prices[i] - min);
        }
        
        return max;
    }
}