Maximum Profit with at Most k Transactions

You are given an array of integers \(nums\) representing the stock prices of a company in chronological order and a positive integer \(k\) representing the maximum number of allowed transactions. A transaction is defined as buying and then later selling one share of the stock. Your task is to determine the maximum profit that can be achieved with at most \(k\) transactions. Note that you cannot engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again). If no profit can be achieved, return 0.

Example 1:

Input: nums = [3, 2, 6, 5, 0, 3], k = 2
Output: 7
Explanation: Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Total profit = 4 + 3 = 7.

Example 2:

Input: nums = [1, 2, 3, 4, 5], k = 1
Output: 4
Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4.

In cases where \(k\) is large relative to the number of days, the problem reduces to finding all profitable pairs.

inputFormat

The first line contains an integer \(n\) indicating the number of stock prices.

The second line contains \(n\) space-separated integers representing the stock prices on each day.

The third line contains a positive integer \(k\) representing the maximum number of transactions allowed.

outputFormat

Output a single integer representing the maximum profit that can be achieved using at most \(k\) transactions. If no profit is possible, output 0.

## sample

6
3 2 6 5 0 3
2

7