Best Time to Buy and Sell Stock V

Medium
1677.

Best Time to Buy and Sell Stock V

Best Time to Buy and Sell Stock V is a medium coding problem on arrays and dynamic programming, asked in Amazon and Bloomberg interviews.

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

You may make at most k transactions, each of one of two kinds:

  • Normal: buy on day i, sell on a later day j > i, earning prices[j] - prices[i].
  • Short selling: sell on day i, buy back on a later day j > i, earning prices[i] - prices[j].

Transactions may not overlap: one must be finished before the next starts, and a new transaction cannot start on the same day the previous one ends.

Return the maximum total profit you can earn.

Example 1

Input
prices = [1,7,9,8,2], k = 2
Output
14
Explanation
Buy on day 0 at 1 and sell on day 2 at 9 (+8); short on day 3 at 8 and buy back on day 4 at 2 (+6).

Example 2

Input
prices = [12,16,19,19,8,1,19,13,9], k = 3
Output
36
Explanation
Buy at 12, sell at 19 (+7); short at 19, buy back at 1 (+18); short at 19, buy back at 8 (+11).

Example 3

Input
prices = [5,5], k = 1
Output
0
Explanation
No transaction can make money.

Constraints

  • 2 <= prices.length <= 10^3
  • 1 <= prices[i] <= 10^6 (the original allows 10^9; capped here so every profit fits a 32-bit integer)
  • 1 <= k <= prices.length / 2
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} prices
 * @param {number} k
 * @return {number}
 */
var maximumProfit = function(prices, k) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Best Time to Buy and Sell Stock V — Problem & Solution

Best Time to Buy and Sell Stock V solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Best Time to Buy and Sell Stock V is a medium coding problem on arrays and dynamic programming, asked in Amazon and Bloomberg interviews.

  • Difficulty: Medium
  • Topics: Arrays, Dynamic Programming
  • Asked at: Amazon, Bloomberg
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

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

You may make at most k transactions, each of one of two kinds:

  • Normal: buy on day i, sell on a later day j > i, earning prices[j] - prices[i].
  • Short selling: sell on day i, buy back on a later day j > i, earning prices[i] - prices[j].

Transactions may not overlap: one must be finished before the next starts, and a new transaction cannot start on the same day the previous one ends.

Return the maximum total profit you can earn.

Example 1

Input: prices = [1,7,9,8,2], k = 2
Output: 14
Explanation: Buy on day 0 at 1 and sell on day 2 at 9 (+8); short on day 3 at 8 and buy back on day 4 at 2 (+6).

Example 2

Input: prices = [12,16,19,19,8,1,19,13,9], k = 3
Output: 36
Explanation: Buy at 12, sell at 19 (+7); short at 19, buy back at 1 (+18); short at 19, buy back at 8 (+11).

Example 3

Input: prices = [5,5], k = 1
Output: 0
Explanation: No transaction can make money.

Constraints

  • 2 <= prices.length <= 10^3
  • 1 <= prices[i] <= 10^6 (the original allows 10^9; capped here so every profit fits a 32-bit integer)
  • 1 <= k <= prices.length / 2

Hints for Best Time to Buy and Sell Stock V

  1. Hint 1

    This is "Best Time to Buy and Sell Stock IV" with a second kind of position: holding a short.

  2. Hint 2

    Track three states per number of completed transactions: free (no position), long (bought, not yet sold) and short (sold, not yet bought back).

  3. Hint 3

    Each day, from yesterday's values: free → long pays -price, free → short earns +price, long → free earns +price and short → free pays -price (both completing a transaction). Using only yesterday's values keeps a transaction from opening on the day another closes.

How to solve Best Time to Buy and Sell Stock V

At the end of any day you are in one of three positions — flat, long or short — and what matters for the future is that position plus how many transactions are already done. A DP over days with those states covers every plan.

Approach

  1. Let free[c], long[c], short[c] be the best balance with c completed transactions; start with free[0] = 0 and everything else -∞.
  2. For each price p, compute new values from the old ones: free[c + 1] = max(free[c + 1], long[c] + p, short[c] - p); long[c] = max(long[c], free[c] - p) and short[c] = max(short[c], free[c] + p) for c < k.
  3. After the last day, return max(free[c]) over c.

Why it works

Every valid schedule is a sequence of non-overlapping intervals, each opened from the flat state and closed back into it, and the DP tracks exactly the position held on each day. Reading only the previous day's values means a position closed today cannot feed a position opened today, which enforces the no-shared-day rule; opening and closing on the same day is likewise impossible.

Complexity

  • Time — O(n · k)
  • Space — O(k)

Pitfalls

  • A short sale is a separate state — you cannot model it as a negative long position in the same array.
  • Update from the previous day's arrays (or iterate carefully); updating in place lets a transaction close and the next one open on the same day.
  • Use 64-bit arithmetic for the -∞ sentinels so -∞ + p cannot wrap around.

Reference solution

Python

from typing import List

def maximumProfit(prices: List[int], k: int) -> int:
    NEG = float('-inf')
    free = [NEG] * (k + 1)
    hold = [NEG] * (k + 1)
    short = [NEG] * (k + 1)
    free[0] = 0
    for p in prices:
        nf, nh, ns = free[:], hold[:], short[:]
        for c in range(k):
            if hold[c] + p > nf[c + 1]:
                nf[c + 1] = hold[c] + p
            if short[c] - p > nf[c + 1]:
                nf[c + 1] = short[c] - p
            if free[c] - p > nh[c]:
                nh[c] = free[c] - p
            if free[c] + p > ns[c]:
                ns[c] = free[c] + p
        free, hold, short = nf, nh, ns
    return int(max(free))

Java

public static int maximumProfit(int[] prices, int k) {
    final long NEG = Long.MIN_VALUE / 4;
    long[] free = new long[k + 1], hold = new long[k + 1], sh = new long[k + 1];
    Arrays.fill(free, NEG);
    Arrays.fill(hold, NEG);
    Arrays.fill(sh, NEG);
    free[0] = 0;
    for (int p : prices) {
        long[] nf = free.clone(), nh = hold.clone(), ns = sh.clone();
        for (int c = 0; c < k; c++) {
            nf[c + 1] = Math.max(nf[c + 1], Math.max(hold[c] + p, sh[c] - p));
            nh[c] = Math.max(nh[c], free[c] - p);
            ns[c] = Math.max(ns[c], free[c] + p);
        }
        free = nf;
        hold = nh;
        sh = ns;
    }
    long best = 0;
    for (long v : free) best = Math.max(best, v);
    return (int) best;
}

C++

int maximumProfit(vector<int>& prices, int k) {
    const long long NEG = LLONG_MIN / 4;
    vector<long long> fr(k + 1, NEG), hold(k + 1, NEG), sh(k + 1, NEG);
    fr[0] = 0;
    for (int p : prices) {
        vector<long long> nf = fr, nh = hold, ns = sh;
        for (int c = 0; c < k; c++) {
            nf[c + 1] = max(nf[c + 1], max(hold[c] + p, sh[c] - p));
            nh[c] = max(nh[c], fr[c] - p);
            ns[c] = max(ns[c], fr[c] + p);
        }
        fr = nf;
        hold = nh;
        sh = ns;
    }
    long long best = 0;
    for (long long v : fr) best = max(best, v);
    return (int) best;
}

JavaScript

var maximumProfit = function(prices, k) {
    var NEG = -Infinity;
    var free = [], hold = [], sh = [];
    for (var c = 0; c <= k; c++) { free.push(NEG); hold.push(NEG); sh.push(NEG); }
    free[0] = 0;
    for (var d = 0; d < prices.length; d++) {
        var p = prices[d];
        var nf = free.slice(), nh = hold.slice(), ns = sh.slice();
        for (var t = 0; t < k; t++) {
            if (hold[t] + p > nf[t + 1]) nf[t + 1] = hold[t] + p;
            if (sh[t] - p > nf[t + 1]) nf[t + 1] = sh[t] - p;
            if (free[t] - p > nh[t]) nh[t] = free[t] - p;
            if (free[t] + p > ns[t]) ns[t] = free[t] + p;
        }
        free = nf; hold = nh; sh = ns;
    }
    var best = 0;
    for (var q = 0; q <= k; q++) if (free[q] > best) best = free[q];
    return best;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming