Maximum profit by buying and selling a share at most k times [Recursive to DP]

Question

I'm not able to break the following problem into overlapping sub-problem unlike other DP problems so DP solution is not intuitive to me.

https://www.geeksforgeeks.org/maximum-profit-by-buying-and-selling-a-share-at-most-k-times/

I see everywhere there is a bottom up approach to solve this. I want to solve it using top-down approach. Like any other problem I want to first come up with recursive solution then use a DP array to cache the result for overlaps. I'm not able to make it overlapping so not able to make DP intuitive. Please help me converting this to DP

Following is my recursive solution.

private int getMaxProfit(ArrayList<Integer> input, int K) {
    return getMaxProfit(input, 0, 0, 0, K, K, 0);
}

private int getMaxProfit(ArrayList<Integer> input, int i, int buy, int sell, int bk, int sk, int bal) {
    if (i == input.size() || (bk == 0 && sk == 0)) { // k times Buying, selling done or we reached end
        return buy > sell ? 0 : sell - buy;
    }

    /** If Buying for k times done **/
    if (bk == 0) {
        int neutral = getMaxProfit(input, i + 1, buy, sell, bk, sk, bal + 1);
        int maxProfitBySell = getMaxProfit(input, i + 1, buy, sell + input.get(i), bk, sk - 1, bal - 1);
        return Math.max(neutral, maxProfitBySell);
    }
    /** If Selling for k times done **/
    if (sk == 0) {
        int neutral = getMaxProfit(input, i + 1, buy, sell, bk, sk, bal + 1);
        int maxProfitByBuy = getMaxProfit(input, i + 1, buy + input.get(i), sell, bk - 1, sk, bal + 1);
        return Math.max(neutral, maxProfitByBuy);
    }
    /** we need to buy one stock before we sell it **/
    if (bal == 0) {
        return getMaxProfit(input, i + 1, buy + input.get(i), sell, bk - 1, sk, bal + 1);
    }
    int maxProfitByBuy = getMaxProfit(input, i + 1, buy + input.get(i), sell, bk - 1, sk, bal + 1); // buy
    int neutral = getMaxProfit(input, i + 1, buy, sell, bk, sk, bal + 1); // dont buy or sell
    int maxProfitBySell = getMaxProfit(input, i + 1, buy, sell + input.get(i), bk, sk - 1, bal - 1); //sell
    return Math.max(neutral, Math.max(maxProfitByBuy, maxProfitBySell));
}

Answer 1

To convert to a bottom-up approach, it can help be more intuitive and easy if the recursive approach is first formulated top-down (meaning the parameters called are decreasing), as well as have an unambiguous association between the parameter state and the result. Since in this problem transactions are sequential and each is composed of two parts, one way we can achieve this is by doubling K and using its current parity to indicate our state in the transactions.

Here is commented top-down in JavaScript, utilising the input examples in the Geeks-for-Geeks link shared in the question description. (Note that here "sells" are examined before their respective "buy".)

// Odd k means the (k/2)th buy was completed
function f(A, k, i=A.length-1){
  // All transactions were done
  if (k == 0)
    return 0
  // We're at the start of the price list
  // so if we are in the middle of a transaction,
  // force the associated "buy"
  if (i == 0)
    return k & 1 ? -A[0] : 0
  
  // Current k is odd so we have completed a "sell" -
  // choose to record the associated "buy" or skip
  if (k & 1){
    return Math.max(
      -A[i] + f(A, k - 1, i - 1), // buy
      f(A, k, i - 1) // skip
    )
  // Current k is even so we have completed a "buy" or
  // are "at rest" - choose to record a new "sell" or skip
  } else {
    return Math.max(
      A[i] + f(A, k - 1, i - 1), // sell
      f(A, k, i - 1) // skip
    )
  }
}

var inputs = [
  [[10, 22, 5, 75, 65, 80], 2], // 87
  [[12, 14, 17, 10, 14, 13, 12, 15], 3], // 12
  [[100, 30, 15, 10, 8, 25, 80], 3], // 72
  [[90, 80, 70, 60, 50], 1] // 0
]

for (let [A, K] of inputs){
  console.log(`A: ${A}, K: ${K}`)
  console.log(f(A, 2*K)) // call with doubled K
}

Now here's the conversion to bottom-up, which is almost identical (O(n2k) = O(nk)):

// Bottom-up
function f(A, k){
  let M = new Array(A.length)
  
  for (let i=0; i<A.length; i++)
    M[i] = new Array(2*k + 1).fill(0)

  // Base case - force buy
  for (let j=1; j<=2*k; j+=2)
    M[0][j] = -A[0]

  for (let i=1; i<A.length; i++){
    for (let j=1; j<=2*k; j++){
      if (j & 1){
        M[i][j] = Math.max(
          -A[i] + M[i-1][j-1], // buy
          M[i - 1][j]
        )
     
      } else {
        M[i][j] = Math.max(
          A[i] + M[i-1][j-1], // sell
          M[i-1][j]
        )
      }
    }
  }

  return M[A.length-1][2*k]
}

var inputs = [
  [[10, 22, 5, 75, 65, 80], 2], // 87
  [[12, 14, 17, 10, 14, 13, 12, 15], 3], // 12
  [[100, 30, 15, 10, 8, 25, 80], 3], // 72
  [[90, 80, 70, 60, 50], 1] // 0
]

for (let [A, K] of inputs){
  console.log(`A: ${A}, K: ${K}`)
  console.log(f(A, K))
}