Share my O(n) O(1) java DP solution with thinking process


  • 0
    F

    For Day i, there would be 5 possible states, let's use A, B, C, D, E represent them.
    A - Before first buy
    B - First buy
    C - First sell
    D- Second Buy
    E- Second Sell

    Following picture shows the state machine(Forgive my bad painting : )) .
    0_1479833717566_tmp.jpg image url)
    So, we got following DP state transition:

    A[i] = A[i-1];
    B[i] = max(B[i-1], A[i-1] - price[i]);
    C[i] = max(C[i-1], B[i-1] + price[i]);
    D[i] = max(D[i-1], C[i-1] - price[i]);
    E[i] = max(E[i-1], D[i-1] + price[i]);

    While A[0] = 0, B[0] = -price[0], C[0] = D[0] = E[0] = INT_MIN. The answer is MAX(A[n-1], C[n-1], D[n-1], E[n-1]). Since A[i] always equals 0, it can be optimized out. And the state[i] always deduced form state[i-1], then the space can be optimized to O(1).

        public int maxProfit(int[] prices) {
            if (prices.length < 2) return 0;
            int B = -prices[0], C = Integer.MIN_VALUE, D = Integer.MIN_VALUE, E = Integer.MIN_VALUE;
            for (int i = 1; i < prices.length; i++) {
                int tb = B, tc = C;
                B = Math.max(tb, -prices[i]);
                C = Math.max(tc, tb + prices[i]);
                if (i > 1) {
                    int td = D;
                    D = Math.max(td, tc - prices[i]);
                    if (i > 2)   E = Math.max(E, td + prices[i]);
                }
            }
            return Math.max(Math.max(C, D), Math.max(0, E));
        }
    

Log in to reply
 

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