At Most K Round Trips
Medium2-D Dynamic Programming
Problem
A trader may make at most k round trips on one share: a round trip is one buy followed later by one sell. At most one share can be held at a time. Daily prices are in prices.
Return the maximum total profit achievable with at most k round trips.
Example 1
- Input:
- k = 2, prices = [4, 2, 7, 1, 5, 3, 8]
- Output:
- 12
Buy at 2, sell at 7 (+5); buy at 1, sell at 8 (+7). A third trip could not be used.
Example 2
- Input:
- k = 1, prices = [4, 2, 7, 1, 5, 3, 8]
- Output:
- 7
The single best trip is 1 → 8.
Constraints
- 0 ≤ k ≤ 100
- 0 ≤ prices.length ≤ 1000
- 0 ≤ prices[i] ≤ 1000
Hint
Show the first hint
Besides 'holding or not', what else do you need to know about the past to decide today?
Walkthrough
How to approach it
01Clarify before coding
- Does an unfinished buy count as a trip? It uses up a trip slot, but it is never profitable to end holding.
- Is k 'at most' or 'exactly'? At most; fewer trips are allowed.
- Can prices be empty or k be 0? Yes, both give 0.
02Brute force
Choose up to k non-overlapping (buy day, sell day) pairs in every possible way.
Cost: Roughly O(n^(2k)): already 10^12 for k = 2 and n = 1000.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.