0776MediumArrayDynamic Programming

Freight Slot Trading Desk

Tracked in this browser only

Trains the technique from

LeetCode 3573Best Time to Buy and Sell Stock V

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

prices[i] is the quoted price of one freight slot on day i. You run a desk that may complete at most k trades over those days.

A trade uses two different days i < j and comes in one of two shapes:

a long: take the slot on day i and hand it back on day j, for a gain of prices[j] - prices[i];
a short: promise the slot on day i and cover the promise on day j, for a gain of prices[i] - prices[j].

Only one trade may be open at a time, so a trade has to be closed before the next one opens. A new trade may open on the very same day the previous one closes. You may complete fewer than k trades, and completing none is allowed, in which case the total is 0.

Return the largest total gain you can finish with.

Examples

Example 1

Input: prices = [5,1,9,2], k = 2
Output: 15

One allowed pair of trades: a long taken on day 1 at 1 and handed back on day 2 at 9 gains 8, then a short promised on day 2 at 9 and covered on day 3 at 2 gains 7. The second trade opens on the day the first one closes, which the rules permit, and the total is 15.

Example 2

Input: prices = [9,4], k = 1
Output: 5

The one trade allowed is a short promised on day 0 at 9 and covered on day 1 at 4, which gains 9 - 4 = 5.

Example 3

Input: prices = [6,6,6,6,6,6], k = 3
Output: 0

Every quote is the same, so any trade in either direction gains 0. Completing no trades at all is allowed, so the total is 0.

Constraints

2 <= prices.length <= 10^3
1 <= prices[i] <= 10^9
1 <= k <= 500
2 * k <= prices.length

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def maximum_profit(prices: list[int], k: int) -> int:

Java

public long maximumProfit(int[] prices, int k)

The intended approach

Time O(n * k) for n days and a cap of k trades: each day updates each of the three arrays over all trade counts.Space O(k) for the three arrays plus the two one-day copies.

Sweep the days once carrying three arrays indexed by the number of trades already closed: `flat` for having nothing open, `up` for a long open with its opening quote already subtracted, `down` for a short open with its opening quote already added. On each day first close positions using yesterday's `up` and `down`, which is what keeps the two days of a trade distinct, then allow a fresh position to open from today's `flat`, which is what lets one trade start on the day another ends. The answer is the best `flat` entry at the end.

Pythonentry point: maximum_profit

def maximum_profit(prices, k):
    # Day-by-day state machine. flat[t] is the best running total after t closed
    # trades with nothing open, up[t] the best with a long open and down[t] the
    # best with a short open (the opening quote already folded in).
    # Time O(n * k), space O(k).
    NEG = -(1 << 62)
    flat = [NEG] * (k + 1)
    flat[0] = 0
    up = [NEG] * (k + 1)
    down = [NEG] * (k + 1)
    for p in prices:
        # positions that may be closed today are the ones opened on an earlier day
        prev_up = up[:]
        prev_down = down[:]
        for t in range(k, 0, -1):
            best = flat[t]
            if prev_up[t - 1] > NEG and prev_up[t - 1] + p > best:
                best = prev_up[t - 1] + p
            if prev_down[t - 1] > NEG and prev_down[t - 1] - p > best:
                best = prev_down[t - 1] - p
            flat[t] = best
        # a fresh position may open today, including on the day one just closed
        for t in range(k + 1):
            if flat[t] > NEG:
                if flat[t] - p > up[t]:
                    up[t] = flat[t] - p
                if flat[t] + p > down[t]:
                    down[t] = flat[t] + p
    return max(flat)

The obvious version

Table over (trades left, first day still available). For each state try skipping the day, or pairing it with every later day in either direction and continuing from the closing day. Cubic-ish but it enumerates trades directly instead of tracking states.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_maximum_profit(prices, k):
    n = len(prices)
    # dp[t][i] = best total from day i onward using at most t trades, filled by
    # enumerating every possible pair of days for the next trade.
    dp = [[0] * (n + 1) for _ in range(k + 1)]
    for t in range(1, k + 1):
        for i in range(n - 1, -1, -1):
            best = dp[t][i + 1]
            for j in range(i + 1, n):
                gain = prices[j] - prices[i]
                rest = dp[t - 1][j]
                if gain + rest > best:
                    best = gain + rest
                if rest - gain > best:
                    best = rest - gain
            dp[t][i] = best
    return dp[k][0]

How this problem was checked

Reference solution executed against 17 test cases — 17 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in