Best Time to Buy and Sell Stock IV

HARD

Description

You are given an integer array prices where prices[i] is the price of a given stock on the i^th 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

Checkout 3 different approaches to solve Best Time to Buy and Sell Stock IV. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Recursion

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

Define a recursive function solve(index, k, isHolding).
Base Case: If index >= prices.length or we cannot make any more transactions, return 0.
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.
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.
The initial call to the function would be solve(0, k, false).

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 Analysis

Time Complexity: O(2^n)Space Complexity: O(n)

Pros and Cons

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.

Code Solutions

Checking out 4 solutions in different languages for Best Time to Buy and Sell Stock IV. Click on different languages to view the code.

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 Solution

Watch the video walkthrough for Best Time to Buy and Sell Stock IV

Patterns:

Dynamic Programming

Data Structures:

Array

Companies:

Goldman Sachs |Google |Nielsen |Nvidia |