Scale Engineer

Best Time to Buy and Sell Stock IV

Hard
#0178Time: O(2^n)Space: O(n)8 companies
Patterns
Dynamic Programming
Data structures
Array
Companies
Goldman SachsGoogleNielsenNvidia

Prompt

You are given an integer array prices where prices[i] is the price of a given stock on the ith day, and an integer k.

Find the maximum profit you can achieve. You may complete at most k transactions: i.e. you may buy at most k times and sell at most k times.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

 

Example 1:

Input: k = 2, prices = [2,4,1]
Output: 2
Explanation: Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.

Example 2:

Input: k = 2, prices = [3,2,6,5,0,3]
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.

 

Constraints:

  • 1 <= k <= 100
  • 1 <= prices.length <= 1000
  • 0 <= prices[i] <= 1000

Approaches

3 approaches with complexity analysis and trade-offs.

This approach attempts to solve the problem by exploring every possible sequence of transactions. It uses a recursive function that, for each day, decides between the possible actions: buy, sell, or do nothing. This generates a decision tree of all possibilities, and the path with the maximum profit is chosen.

Algorithm

  1. Define a recursive function solve(index, k, isHolding).
  2. Base Case: If index >= prices.length or we cannot make any more transactions, return 0.
  3. If isHolding is true (we have a stock):
    • Calculate profit from selling today: prices[index] + solve(index + 1, k - 1, false).
    • Calculate profit from holding: solve(index + 1, k, true).
    • Return the maximum of these two options.
  4. If isHolding is false (we don't have a stock):
    • Calculate profit from buying today: -prices[index] + solve(index + 1, k, true).
    • Calculate profit from skipping today: solve(index + 1, k, false).
    • Return the maximum of these two options.
  5. The initial call to the function would be solve(0, k, false).

Walkthrough

The core of this method is a recursive function, let's call it solve(day, transactions_completed, holding). This function calculates the maximum profit achievable from a given day onwards, given that we have already completed transactions_completed and our holding status (whether we own a stock or not).

  • State: The state is defined by (day, transactions_completed, holding).
  • Transitions:
    • If we are holding a stock, we can either sell it today (which increments transactions_completed) or hold it and move to the next day.
    • If we are not holding a stock, we can either buy one today (which changes our holding status) or skip today and move on.
  • Base Cases: The recursion stops when we have exhausted the days (day >= prices.length) or completed the maximum allowed transactions (transactions_completed >= k). In these scenarios, no further profit can be made, so we return 0.

The final answer is the result of the initial call solve(0, 0, false).

class Solution {    public int maxProfit(int k, int[] prices) {        return solve(0, 0, 0, k, prices);    }     private int solve(int day, int transactions, int holding, int k, int[] prices) {        // Base case: no more days to trade or max transactions reached        if (day >= prices.length || transactions >= k) {            return 0;        }         // Recursive step        // Option 1: Do nothing today (rest)        int restProfit = solve(day + 1, transactions, holding, k, prices);         int actionProfit;        if (holding == 1) {            // Option 2: Sell the stock            actionProfit = prices[day] + solve(day + 1, transactions + 1, 0, k, prices);        } else { // holding == 0            // Option 3: Buy the stock            actionProfit = -prices[day] + solve(day + 1, transactions, 1, k, prices);        }                return Math.max(restProfit, actionProfit);    }}

Complexity

Time

O(2^n)

Space

O(n)

Trade-offs

Pros

  • Conceptually straightforward and follows the problem statement directly.

Cons

  • Extremely inefficient due to exponential time complexity.

  • Results in 'Time Limit Exceeded' for even moderately sized inputs.

  • Redundantly computes the same subproblems multiple times.

Solutions

public class Solution {    public int MaxProfit(int k, int[] prices) {        int n = prices.Length;        int[, ] f = new int[k + 1, 2];        for (int j = 1; j <= k; ++j) {            f[j, 1] = -prices[0];        }        for (int i = 1; i < n; ++i) {            for (int j = k; j > 0; --j) {                f[j, 0] = Math.Max(f[j, 1] + prices[i], f[j, 0]);                f[j, 1] = Math.Max(f[j - 1, 0] - prices[i], f[j, 1]);            }        }        return f[k, 0];    }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem