Best Time to Buy and Sell Stock IV LeetCode solution in Java

1
class Solution {
2
  public int maxProfit(int k, int[] prices) {
3
    int transaction = k;
4
    int N = prices.length;
5
    int[][][] dp = new int[N][2][k + 1];
6
    for (int i = 0; i < N; i++) {
7
      for (int j = 0; j < 2; j++) {
8
        for (int tran = 0; tran <= k; tran++) {
9
          dp[i][j][tran] = -1;
10
        }
11
      }
12
    } // init dp
13
    return profit(0, 1, k, prices, dp);
14
  }
15

16
  int profit(int index, int buy, int transaction, int[] prices, int[][][] dp) {
17
    if (transaction == 0) {
18
      return 0;
19
    }
20
    if (index == prices.length) {
21
      return 0;
22
    }
23
    if (dp[index][buy][transaction] != -1) {
24
      return dp[index][buy][transaction];
25
    }
26
    int profit = 0;
27
    if (buy == 1) {
28
      profit =
29
          Math.max(
30
              -prices[index] + profit(index + 1, 0, transaction, prices, dp),
31
              0 + profit(index + 1, 1, transaction, prices, dp));
32
    } else {
33
      profit =
34
          Math.max(
35
              prices[index] + profit(index + 1, 1, transaction - 1, prices, dp),
36
              0 + profit(index + 1, 0, transaction, prices, dp));
37
    }
38
    dp[index][buy][transaction] = profit;
39
    return dp[index][buy][transaction];
40
  }
41
}