Maximum Stock Profit with At Most K Transactions

You are given the stock prices for N consecutive days, and you are allowed to complete at most K transactions. A single transaction consists of buying on one day and selling on a later day. Your task is to calculate the maximum profit you can achieve from these transactions.

If you are allowed to execute an unlimited number of transactions (i.e. if K is large enough), the maximum profit is obtained by summing up all positive differences between consecutive days, i.e., $$\text{Profit} = \sum_{i=1}^{N-1}\max(0, \text{prices}[i] - \text{prices}[i-1]).$$

Otherwise, dynamic programming is used to calculate the maximum profit with at most K transactions.

inputFormat

The first line of input contains two integers N and K, where N is the number of days and K is the maximum number of allowed transactions. The second line contains N integers representing the stock prices for each day.

outputFormat

Output a single integer representing the maximum profit achievable under the given constraints.

6 2
3 2 6 5 0 3

7