0302MediumArrayDynamic ProgrammingGreedy

Handling Fee Resale

Tracked in this browser only

Trains the technique from

LeetCode 714Best Time to Buy and Sell Stock with Transaction Fee

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.

A scrap yard trades a single bale of copper at a time. quotes[i] is the price the bale fetches on day i, and every completed sale is charged a flat handling fee of commission.

The yard may trade as often as it likes but never holds two bales: a purchase is only allowed with the yard clear, and a sale is only allowed with a bale on the ground. Buying and selling on the same day is permitted. The handling fee is charged once per sale, never on a purchase. A bale still on the ground when the days run out is simply left there and earns nothing.

Return the largest net cash position the yard can finish with, counting each sale as its price minus the purchase price minus the handling fee. Trading nothing at all leaves 0.

Examples

Example 1

Input: quotes = [4,7,5,11,6,12], commission = 3
Output: 7

Buy at 4 and sell at 11, then buy at 6 and sell at 12. The two sales bring in 7 and 6 before fees, and the two fees of 3 leave 7.

Example 2

Input: quotes = [1,4,3,6], commission = 2
Output: 3

Buy at 1 on day 0 and sell at 6 on day 3. That is 5 before the fee and 3 after the single fee of 2.

Constraints

1 <= quotes.length <= 5 * 10^4
1 <= quotes[i] < 5 * 10^4
0 <= commission < 5 * 10^4

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 net_resale_gain(quotes: list[int], commission: int) -> int:

Java

public int netResaleGain(int[] quotes, int commission)

The intended approach

Time O(n)Space O(1)

Sweep the days once carrying the best cash position in each of the two situations the yard can be in: clear, or holding a bale. A sale moves the holding figure into the clear figure at today's price less the fee, and a purchase moves the clear figure into the holding figure at today's price. The clear figure after the last day is the answer.

Pythonentry point: net_resale_gain

def net_resale_gain(quotes, commission):
    # Two running balances: `empty` is the best cash position with the yard clear,
    # `holding` the best position with a bale on the ground.  The handling charge is
    # applied at the moment a sale lands, so each closed trade pays it once.
    # O(n) time, O(1) space.
    empty = 0
    holding = -quotes[0]
    for price in quotes[1:]:
        sold = holding + price - commission
        if sold > empty:
            empty = sold
        bought = empty - price
        if bought > holding:
            holding = bought
    return empty

The obvious version

Recurse day by day over the two situations, branching on wait, sell when holding, and buy when clear, and take the best cash position reachable from day 0.

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_net_resale_gain(quotes, commission):
    n = len(quotes)

    def walk(i, holding):
        if i == n:
            return 0
        best = walk(i + 1, holding)
        if holding:
            cand = quotes[i] - commission + walk(i + 1, False)
            if cand > best:
                best = cand
        else:
            cand = -quotes[i] + walk(i + 1, True)
            if cand > best:
                best = cand
        return best

    return walk(0, False)

How this problem was checked

Reference solution executed against 11 test cases — 11 passed
2 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