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

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

Following picture shows the state machine(Forgive my bad painting : )) .
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));
}
``````

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