Maximum Profit with Limited Transactions

HARD50 pts

You are given an array of daily asset values called prices, where prices[i] represents the value of an asset on day i (0-indexed). You are also given an integer k representing the maximum number of complete trading cycles (buy-sell operations) you are allowed to perform.

Your goal is to determine the maximum profit achievable under the following constraints:

Transaction Limit: You may execute at most k complete transactions. A complete transaction consists of one purchase followed by one sale.
Sequential Constraint: You cannot hold more than one unit of the asset at any time. This means you must sell your current holding before making another purchase.
Timing Flexibility: You can buy and sell on any day, but buying and selling on the same day yields no profit for that transaction.

The challenge lies in strategically selecting which days to buy and sell to maximize your cumulative profit while respecting the transaction limit.

Key Insight: When k is sufficiently large (specifically when k ≥ n/2 where n is the number of days), the transaction limit becomes irrelevant, and you can capture all possible profitable price increases. However, when k is small, you must carefully choose which price movements to capitalize on.

Return the maximum profit you can achieve under these constraints. If no profitable transaction is possible, return 0.

Example

Input

k = 2
prices = [2,4,1]

Output

2

Explanation

With a maximum of 2 transactions allowed, the optimal strategy is: Purchase on day 0 (value = 2), sell on day 1 (value = 4). This single transaction yields a profit of 4 - 2 = 2. Although we have one more transaction available, there's no profitable opportunity after day 1 since the value only drops to 1. Total maximum profit = 2.

Example

Input

k = 2
prices = [3,2,6,5,0,3]

Output

7

Explanation

With a limit of 2 transactions, we can strategically use both: First transaction: Buy on day 1 (value = 2), sell on day 2 (value = 6), profit = 6 - 2 = 4. Second transaction: Buy on day 4 (value = 0), sell on day 5 (value = 3), profit = 3 - 0 = 3. Note that we skip the day 3 value of 5 because selling at 6 and later buying at 0 is more profitable than any alternative. Total maximum profit = 4 + 3 = 7.

Example

Input

k = 1
prices = [1,2,3,4,5]

Output

4

Explanation

With only 1 transaction allowed in a consistently rising market, the optimal strategy is to buy at the lowest point (day 0, value = 1) and sell at the highest point (day 4, value = 5). Profit = 5 - 1 = 4. Note that if we had unlimited transactions, we could achieve the same profit by buying each day and selling the next, but with only one transaction, we must choose the global minimum and maximum.

Accepted0/0·0% Acceptance

Constraints

1 ≤ k ≤ 100
1 ≤ prices.length ≤ 1000
0 ≤ prices[i] ≤ 1000

Code

Visualizer

Solutions

14px

Test Cases3

Results

Submissions

k =

prices =

[2,4,1]

Maximum Profit with Limited Transactions

Hints

Maximum Profit with Limited Transactions

Hints