Maximize Nonoverlapping Trades under a Transaction Cap
Company: Infosys
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Other
### Problem
Given chronological prices and an integer `k`, return the maximum profit from at most k buy/sell transactions. Hold at most one share at a time: a sale must precede another purchase. You may use fewer than k transactions, including none.
```cpp
int maxProfit(int k, vector<int>& prices);
```
### Examples
```text
Input: k = 2, prices = [5,1,6,2,8]
Output: 11
```
The two gains are 6-1 and 8-2.
```text
Input: k = 1, prices = [5,1,6,2,8]
Output: 7
```
### Constraints
- `1 <= k <= 100`.
- There are between 1 and 1000 prices, each between 0 and 1000.
- Transactions cannot overlap.
Overview: Maximize profit under an arbitrary transaction cap with reachable cash and holding states indexed by completed sales.