Best Time to Buy and Sell Stock k times like Best Time to Buy and Sell Stock III

Note: This is a TLE version. O(n^3). but, easier to understand

        |
        |   * * 
 *      |  *   * *
* *     | *       *
*   *    |*         *
    *   |           *   * *
     * *|            * *
        |             *
        |
        i

day i separates days into 0..i and i..end. just assume that you know max profit k - 1 times for 0..i day is maxProfit(k - 1, 0..i).

such that

the max profit of buy and sell only once after day i is maxProfit(k - 1, 0..i) + maxProfit(1, i..end). just do as Best Time to Buy and Sell Stock III, brute force i to find the max profit.

maxProfit(k, m..n) = {
  
  if k == 1 then 
    return call maxProfit1(m..n) // best buy and sell once
  else
    return 
    MAX { 
      for i = 0 .. end
        maxProfit(k - 1, m..i) + maxProfit(1, i..n)
    }
}

when k = 2

the func becomes Best Time to Buy and Sell Stock III

    return MAX { 
      for i = 0 .. end
        maxProfit1(m..i) + maxProfit1(i..n) // m..i is left part and i..n is right part
    }

Maximum Subarray like version

I dont like this because I dont think it is easy to understand. However, this will reduce the time complexity from O(n^3) to O(n^2).

Start from Best Time to Buy and Sell Stock

In the Maximum Subarray, numbers are always added to the variable history. when the history goes below zero, just drop it.

This is like you and a fool buy and sell stock together, the fool buys and sells his stocks everyday. Whenever the fool earns more money than you at day i, you could act like fool to get to max profit from day 0 to day i. otherwise, just keep the max profit. Sometimes, the fool may go broke, just change another fool.

Talk is cheap, show you the code

public int maxProfit(int[] prices) {
    
    if(prices.length < 1) return 0;

    int[] P = new int[prices.length];  // this is you
    int[] H = new int[prices.length];  // this is that fool
                                       // H is short for history like Maximum Subarray

    for(int i = 1; i < prices.length; i++){
        int p = prices[i] - prices[i - 1];

        H[i] = Math.max(H[i - 1] + p, 0); // buy and sell
                                          // max(H, 0) means when fool goes broke, just start from another

        P[i] = Math.max(H[i], P[i - 1]);  // if the fool earns more than you
                                          // time to act like the fool to get max profit
    }

    return P[prices.length - 1];        
}

Extends to K times

just exntends P and H to 2d. P[time][day]

the only difference is change

H[j][i] = Math.max(H[j][i - 1] + p, 0);

to

H[j][i] = Math.max(H[j][i - 1] + p, P[j - 1][i - 1]);

that means the fool should act better than buy and sell k - 1 times until day i - 1 (P[k - 1][i - 1]), or the fool should restart from P[k - 1][i - 1] in order to get better profit.

int[][] P = new int[k + 1][prices.length];
int[][] H = new int[k + 1][prices.length];

for(int j = 1; j <= k; j++) { 

    for (int i = 1; i < prices.length; i++) {
        int p = prices[i] - prices[i - 1];

        H[j][i] = Math.max(H[j][i - 1] + p, P[j - 1][i - 1]);

        P[j][i] = Math.max(H[j][i], P[j][i - 1]);
    }
}

Final cheat

I did some optimization to avoid TLE, like caching the difference of price i and price i - 1 into D. but leetcode still reject my code.

I found some test cases is really big, but can be got O(n) using Best Time to Buy and Sell Stock II because k > len(prices).