Cacher is the code snippet organizer for pro developers

/*
理解思路和The order of maxProfit2, lowestBuyPrice2, maxProfit1, lowestBuyPrice1
lowestBuyPrice2 = min(p - maxProfit1[high] + maxProfit1[low])
*/


class Solution {
	public static int maxProfit(int [] prices){
	    int maxProfit1 = 0; 
	    int maxProfit2 = 0; 
	    int lowestBuyPrice1 = Integer.MAX_VALUE;
	    int lowestBuyPrice2 = Integer.MAX_VALUE;
	   
	    for(int p:prices){
	    	maxProfit2 = Math.max(maxProfit2, p - lowestBuyPrice2);
            // lowestBuyPrice2 = min(p - maxProfit1[high] + maxProfit1[low])
	    	lowestBuyPrice2 = Math.min(lowestBuyPrice2, p - maxProfit1);
	    	maxProfit1 = Math.max(maxProfit1, p - lowestBuyPrice1);
	    	lowestBuyPrice1 = Math.min(lowestBuyPrice1, p);
	    }
	    return maxProfit2;
    }
}

/*
T[i][j], i = transaction, j = jth day
                T[i][j - 1], not transacting on jth day
              /
T[i][j] = max 
              \
                T[i - 1][m] + (prices[i] - prices[m]), for m = 0,..., j - 1
                best you can get by completing transaction on jth day
*/


class Solution {
    public int maxProfit(int[] prices) {
        return maxProfitSlowSolution(prices, 2);
    }
    
    
    public int maxProfitSlowSolution(int prices[], int K) {
        if (K == 0 || prices.length == 0) {
            return 0;
        }

        int T[][] = new int[K+1][prices.length];

        for (int i = 1; i < T.length; i++) {
            for (int j = 1; j < T[0].length; j++) {
                int maxVal = 0;
                for (int m = 0; m < j; m++) {
                    maxVal = Math.max(maxVal, prices[j] - prices[m] + T[i-1][m]);
                }
                T[i][j] = Math.max(T[i][j-1], maxVal);
            }
        }
        // printActualSolution(T, prices);
        return T[K][prices.length - 1];
    }
    
    
    //use stack to store the order
    public void printActualSolution(int T[][], int prices[]) {
        int i = T.length - 1;
        int j = T[0].length - 1;

        Deque<Integer> stack = new LinkedList<>();
        while(true) {
            if(i == 0 || j == 0) {
                break;
            }
            if (T[i][j] == T[i][j-1]) {
                j = j - 1;
            } else {
                stack.addFirst(j);
                int maxDiff = T[i][j] - prices[j];
                for (int k = j-1; k >= 0; k--) {
                    if (T[i-1][k] - prices[k] == maxDiff) {
                        i = i - 1;
                        j = k;
                        stack.addFirst(j);
                        break;
                    }
                }
            }
        }

        while(!stack.isEmpty()) {
            System.out.println("Buy at price " + prices[stack.pollFirst()]);
            System.out.println("Sell at price " + prices[stack.pollFirst()]);
        }
    }
}