Best Time to Buy and Sell Stock V - Problem

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

You are allowed to make at most k transactions, where each transaction can be either of the following:

Normal transaction: Buy on day i, then sell on a later day j where i < j. You profit prices[j] - prices[i].
Short selling transaction: Sell on day i, then buy back on a later day j where i < j. You profit prices[i] - prices[j].

Note that you must complete each transaction before starting another. Additionally, you can't buy or sell on the same day you are selling or buying back as part of a previous transaction.

Return the maximum total profit you can earn by making at most k transactions.

Input & Output

Example 1 — Basic Case with k=2

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

› Output: 5

💡 Note: Best strategy: Buy at price 2, sell at 4 (profit +2), then short sell at 4, buy back at 1 (profit +3). Total profit = 2 + 3 = 5.

Example 2 — Single Transaction

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

› Output: 3

💡 Note: One transaction: Buy at price 1, sell at price 4 for profit of 3. Alternatively, short sell at 3, buy back at 1 for same profit.

Example 3 — No Profit Possible

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

› Output: 0

💡 Note: All prices are the same, so no profit can be made from any transaction.

Constraints

1 ≤ prices.length ≤ 1000
0 ≤ prices[i] ≤ 1000
0 ≤ k ≤ 100

Visualization

Tap to expand

Asked in

G Google 35 a Amazon 28 M Microsoft 22 A Apple 18

The key insight is to use dynamic programming with states tracking holding positions (long, short, or cash) and remaining transactions. The optimal approach uses space-optimized DP with rolling arrays. Time: O(n × k), Space: O(k).

Common Approaches

✓ 2D Dynamic Programming

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

Build a 2D DP table where dp[i][j] represents the maximum profit on day i with j transactions completed. Track multiple states: holding stock, short position, and completed transactions.

Brute Force

⏱️ Time: O(4^n) Space: O(k)

Generate all possible ways to make k transactions (both normal and short selling) and find the maximum profit. For each day, try all possible actions: buy, sell, short sell, or buy back.

Memoization

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

Use recursive approach with memoization to avoid recalculating the same states. Cache results based on day, remaining transactions, holding status, and short position status.

Space-Optimized DP

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

Since each day only depends on the previous day, we can reduce space complexity by using rolling arrays. Keep only two arrays: previous day states and current day states.

2D Dynamic Programming — Algorithm Steps

Initialize DP table with base cases
Fill table for each day and transaction count
Consider all possible actions at each state
Return maximum profit from final states

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize Table

Set up DP table with base cases

Fill States

Compute optimal profit for each day-transaction pair

Final Answer

Maximum profit from all valid final states

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 solution(int* prices, int n, int k) {
    if (k == 0 || n <= 1) return 0;
    
    if (k >= n / 2) {
        int profit = 0;
        for (int i = 1; i < n; i++) {
            profit += max(0, prices[i] - prices[i-1]);
            profit += max(0, prices[i-1] - prices[i]);
        }
        return profit;
    }
    
    int (*dp)[k+1][3] = malloc((n+1) * sizeof(*dp));
    
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            for (int l = 0; l < 3; l++) {
                dp[i][j][l] = INT_MIN / 2;
            }
        }
    }
    
    for (int j = 0; j <= k; j++) {
        dp[0][j][0] = 0;
    }
    
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= k; j++) {
            int price = prices[i - 1];
            
            dp[i][j][0] = dp[i-1][j][0];
            if (j > 0) {
                dp[i][j][0] = max(dp[i][j][0], dp[i-1][j-1][1] + price);
                dp[i][j][0] = max(dp[i][j][0], dp[i-1][j-1][2] - price);
            }
            
            dp[i][j][1] = max(dp[i-1][j][1], dp[i-1][j][0] - price);
            dp[i][j][2] = max(dp[i-1][j][2], dp[i-1][j][0] + price);
        }
    }
    
    int result = 0;
    for (int j = 0; j <= k; j++) {
        result = max(result, dp[n][j][0]);
    }
    
    free(dp);
    return result;
}

void parseArray(const char* str, int* arr, int* size) {
    *size = 0;
    const char* p = str;
    while (*p && *p != '[') p++;
    if (*p == '[') p++;
    while (*p && *p != ']') {
        while (*p == ' ' || *p == ',') p++;
        if (*p == ']' || *p == '\0') break;
        arr[(*size)++] = (int)strtol(p, (char**)&p, 10);
    }
}

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

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

Iterate through n days and k transactions, constant work per state

✓ Linear Growth

Space Complexity

O(n × k)

2D DP table stores states for all day-transaction combinations

✓ Linear Space

32.0K Views

Medium Frequency

~35 min Avg. Time

850 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 V - Problem

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

2D Dynamic Programming — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler