Best Time to Buy and Sell Stocks III

Say you have an array, A, 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 2 transactions.

Return the maximum possible profit.

Note: You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

The first and the only argument is an integer array, A.

Return an integer, representing the maximum possible profit.

1 <= length(A) <= 7e5
1 <= A[i] <= 1e7

Input 1:
    A = [1, 2, 1, 2]

Output 1:
    2

Explanation 1: 
    Day 0 : Buy 
    Day 1 : Sell
    Day 2 : Buy
    Day 3 : Sell

Input 2:
    A = [7, 2, 4, 8, 7]

Output 2:
    6

Explanation 2:
    Day 1 : Buy
    Day 3 : Sell

Solution:

Time: O(n)
Space: O(n)

public class Solution {
    // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
    public int maxProfit(final int[] A) {
        // dp[d][k][s] = max profit of dp[day][number of transactions made][has stock or not]
        // dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + A[i])
        // dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - A[i]]
        if (A == null || A.length == 0) return 0;
        int n = A.length;
        int[][][] dp = new int[n + 1][3][2];
        dp[0][0][1] = Integer.MIN_VALUE;
        dp[0][1][1] = Integer.MIN_VALUE;
        dp[0][2][1] = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i ++) {
            for (int k = 1; k <= 2; k ++) {
                dp[i][k][0] = Math.max(dp[i - 1][k][0], dp[i - 1][k][1] + A[i - 1]);
                dp[i][k][1] = Math.max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - A[i - 1]);
            }
        }
        return dp[n][2][0];
    }
}

Solution2:

Time: O(n)
Space: O(1)

public class Solution {
    // DO NOT MODIFY THE ARGUMENTS WITH "final" PREFIX. IT IS READ ONLY
    public int maxProfit(final int[] A) {
        // dp[d][k][s] = max profit of dp[day][number of transactions made][has stock or not]
        // dp[i][k][0] = max(dp[i - 1][k][0], dp[i - 1][k][1] + A[i])
        // dp[i][k][1] = max(dp[i - 1][k][1], dp[i - 1][k - 1][0] - A[i]]
        
        // dp[i][1][0] = max(dp[i - 1][1][0], dp[i - 1][1][1] + A[i])
        // dp[i][1][1] = max(dp[i - 1][1][1], dp[i - 1][0][0] (=0) - A[i]]
        // dp[i][2][0] = max(dp[i - 1][2][0], dp[i - 1][2][1] + A[i])
        // dp[i][2][1] = max(dp[i - 1][2][1], dp[i - 1][1][0] - A[i]]
        if (A == null || A.length == 0) return 0;
        int n = A.length;
        int dp_1_0 = 0;
        int dp_1_1 = Integer.MIN_VALUE;
        int dp_2_0 = 0;
        int dp_2_1 = Integer.MIN_VALUE;
        for (int i = 1; i <= n; i ++) {
            dp_2_0 = Math.max(dp_2_0, dp_2_1 + A[i - 1]);
            dp_2_1 = Math.max(dp_2_1, dp_1_0 - A[i - 1]);
            dp_1_0 = Math.max(dp_1_0, dp_1_1 + A[i - 1]);
            dp_1_1 = Math.max(dp_1_1, - A[i - 1]);
        }
        return dp_2_0;
    }
}