Best Time to Buy and Sell Stock IV - Problem

You're a stock trader with limited transactions - you can make at most k complete buy-sell cycles to maximize your profit.

Given an array prices where prices[i] represents the stock price on day i, and an integer k representing the maximum number of transactions allowed, find the maximum profit you can achieve.

Important constraints:

You must sell before buying again (no simultaneous transactions)
A transaction consists of buying AND then selling a stock
You can complete at most k transactions

Example: If prices = [2,4,1] and k = 2, you can buy at 2, sell at 4 (profit = 2), but there's no profitable second transaction, so maximum profit is 2.

Input & Output

example_1.py — Basic Case

$ Input: k = 2, prices = [2,4,1]

› Output: 2

💡 Note: Buy at price 2, sell at price 4. Profit = 4 - 2 = 2. No profitable second transaction possible.

example_2.py — Multiple Transactions

$ Input: k = 2, prices = [3,2,6,5,0,3]

› Output: 7

💡 Note: Buy at price 2, sell at price 6 (profit = 4). Buy at price 0, sell at price 3 (profit = 3). Total = 7.

example_3.py — Edge Case

$ Input: k = 2, prices = [1,2,3,4,5]

› Output: 4

💡 Note: One transaction is optimal: buy at 1, sell at 5 for profit of 4. Multiple smaller transactions don't yield more profit.

Constraints

0 ≤ k ≤ 100
0 ≤ prices.length ≤ 1000
0 ≤ prices[i] ≤ 1000
Time limit: 2 seconds per test case

Visualization

Tap to expand

Asked in

G Google 42 a Amazon 38 ⊞ Microsoft 31 Apple 24 f Meta 19

The optimal solution uses dynamic programming to track buy and sell states for each transaction. Key insight: maintain buy[i] (max profit after buying in transaction i) and sell[i] (max profit after selling in transaction i). Time complexity: O(n*k), Space: O(k).

Common Approaches

✓ Dynamic Programming (Optimal)

⏱️ Time: O(n*k) Space: O(k)

Use dynamic programming to track the maximum profit for two states per transaction: after buying (buy[i]) and after selling (sell[i]). For each price, update all possible transaction states optimally.

Recursive Brute Force

⏱️ Time: O(3^n) Space: O(n)

Generate all possible ways to select k buy-sell pairs from the price array and calculate maximum profit. This involves recursively trying to buy and sell at each position.

Dynamic Programming (Optimal) — Algorithm Steps

Initialize buy[i] = -infinity (no money to buy) and sell[i] = 0 (no profit yet)
For each price, update all transaction states from k down to 1
buy[i] = max(buy[i], sell[i-1] - price) - best profit after buying for transaction i
sell[i] = max(sell[i], buy[i] + price) - best profit after selling for transaction i
Return sell[k] as the maximum profit after k transactions

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize States

buy[i] = -∞ (can't buy without money), sell[i] = 0 (no profit initially)

Process Each Price

For each price, update all transaction states from k down to 1

Update Sell State

sell[i] = max(previous sell[i], buy[i] + current price)

Update Buy State

buy[i] = max(previous buy[i], sell[i-1] - current price)

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int max(int a, int b) {
    return a > b ? a : b;
}

int maxProfit(int k, int* prices, int pricesSize) {
    if (pricesSize == 0 || k == 0) return 0;
    
    // Optimization for large k
    if (k >= pricesSize / 2) {
        int profit = 0;
        for (int i = 1; i < pricesSize; i++) {
            if (prices[i] > prices[i-1]) {
                profit += prices[i] - prices[i-1];
            }
        }
        return profit;
    }
    
    int* buy = (int*)malloc((k + 1) * sizeof(int));
    int* sell = (int*)malloc((k + 1) * sizeof(int));
    
    for (int i = 0; i <= k; i++) {
        buy[i] = INT_MIN;
        sell[i] = 0;
    }
    
    for (int p = 0; p < pricesSize; p++) {
        for (int i = k; i >= 1; i--) {
            sell[i] = max(sell[i], buy[i] + prices[p]);
            buy[i] = max(buy[i], sell[i-1] - prices[p]);
        }
    }
    
    int result = sell[k];
    free(buy);
    free(sell);
    return result;
}

int main() {
    int k;
    scanf("%d", &k);
    
    char line[10000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    int prices[1000];
    int count = 0;
    
    if (strlen(line) > 1) {
        char* token = strtok(line, ",\n");
        while (token != NULL) {
            prices[count++] = atoi(token);
            token = strtok(NULL, ",\n");
        }
    }
    
    printf("%d\n", maxProfit(k, prices, count));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n*k)

We process each of n prices and update k transaction states

✓ Linear Growth

Space Complexity

O(k)

We only need to store buy and sell states for k transactions

⚡ Linearithmic Space

89.3K Views

High Frequency

~35 min Avg. Time

2.8K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Best Time to Buy and Sell Stock IV - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Dynamic Programming (Optimal) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler