Maximum Profit with At Most K Transactions

You are given an integer \( k \) and a sequence of daily stock prices. Your task is to calculate the maximum profit achievable with at most \( k \) transactions. A transaction consists of one buy and one sell operation, and you must sell before you buy again. If no profit is possible, return 0.

A dynamic programming approach can solve the problem efficiently. One common method is to define \( dp[i][j] \) as the maximum profit achievable with at most \( i \) transactions up to day \( j \). This relationship can be formulated as:

\( dp[i][j] = \max(dp[i][j-1], prices[j] + \max_{0 \leq m < j}(dp[i-1][m] - prices[m])) \)

Implement an efficient solution to pass all test cases.

inputFormat

The input consists of three parts provided via standard input:

1. The first line contains a single integer \( k \), the maximum number of transactions allowed.
2. The second line contains a single integer \( n \), the number of days or the number of price entries.
3. The third line contains \( n \) space-separated integers representing the stock prices for each day. If \( n \) is 0, this line may be empty.

outputFormat

Output a single integer on standard output representing the maximum profit that can be made with at most \( k \) transactions.

1
7
2 4 3 6 1 3

4