DP #123 Best Time to Buy and Sell Stock III

class Solution {
    public int maxProfit(int[] prices) {
        // int n = prices.length;
        // int[][][] dp = new int[n][2][3];
        // for (int[][] r2 : dp)
        // for (int[] r : r2)
        // Arrays.fill(r, -1);
        // return recur(0, 1, 0, prices, n, dp);
        return tabOpt(prices);
    }

    // Space optimised Tabulation solution
    public int tabOpt(int[] pr) {
        int n = pr.length;
        int[][] dp = new int[2][3];
        for (int i = n - 1; i >= 0; i--) {
            int[][] cur = new int[2][3];
            for (int b = 1; b >= 0; b--) {
                for (int t = 2; t >= 0; t--) {
                    if (b == 1) {
                        if (t == 2)
                            cur[b][t] = 0;
                        else
                            cur[b][t] = Math.max(-pr[i] + dp[1 - b][t + 1], dp[b][t]);
                    } else {
                        cur[b][t] = Math.max(pr[i] + dp[1 - b][t], dp[b][t]);
                    }
                }
            }
            dp = cur;
        }
        return dp[1][0];
    }

    // Tabulation solution
    public int tab(int[] pr) {
        int n = pr.length;
        int[][][] dp = new int[n + 1][2][3];
        for (int i = n - 1; i >= 0; i--) {
            for (int b = 1; b >= 0; b--) {
                for (int t = 2; t >= 0; t--) {
                    if (b == 1) {
                        if (t == 2)
                            dp[i][b][t] = 0;
                        else
                            dp[i][b][t] = Math.max(-pr[i] + dp[i + 1][1 - b][t + 1], dp[i + 1][b][t]);
                    } else {
                        dp[i][b][t] = Math.max(pr[i] + dp[i + 1][1 - b][t], dp[i + 1][b][t]);
                    }
                }
            }
        }
        return dp[0][1][0];
    }

    // Recursive solution
    public int recur(int i, int b, int t, int[] pr, int n, int[][][] dp) {
        if (i == n)
            return 0;
        if (dp[i][b][t] != -1)
            return dp[i][b][t];
        if (b == 1) {
            if (t == 2)
                return dp[i][b][t] = 0;
            return dp[i][b][t] = Math.max(-pr[i] + recur(i + 1, 1 - b, t + 1, pr, n, dp),
                    recur(i + 1, b, t, pr, n, dp));
        } else {
            return dp[i][b][t] = Math.max(pr[i] + recur(i + 1, 1 - b, t, pr, n, dp), recur(i + 1, b, t, pr, n, dp));
        }
    }
}