hardDynamic Programming 1DPure DSA~40 min
Max Profit With At Most K Trades
Daily prices of an asset are known in advance. You may complete at most k buy→sell trades, never holding more than one position at a time. Maximize total profit.
Problem
Given an integer k and an array prices where prices[i] is the price on day i, return the maximum profit from at most k transactions. You must sell before buying again.
Input
An integer k and an integer array prices.
Output
An integer — the maximum achievable profit.
Constraints
- 0 ≤ k ≤ 100
- 1 ≤ n ≤ 1000
- 0 ≤ prices[i] ≤ 1000
Examples
Example 1
Input
k=2 prices=[3,2,6,5,0,3]
Output
7
Buy@2 sell@6 (+4), buy@0 sell@3 (+3) → 7.
Example 2
Input
k=2 prices=[2,4,1]
Output
2
Buy@2 sell@4 (+2); the third day adds nothing.