Best Time To Buy and Sell Stock Problem Statement

You are given an array 'PRICES' of 'N' integers, where 'PRICES[i]' represents the price of a certain stock on the i-th day. An integer 'K' is also provided, indicating the maximum number of transactions you can perform.

Your task is to determine the maximum profit achievable with at most K transactions. A valid transaction would require buying a stock before selling it.

Note:

You cannot engage in multiple transactions simultaneously, meaning you must sell a stock before buying it again.

Example:

Input:

N = 6, PRICES = [3, 2, 6, 5, 0, 3], K = 2

Output:

7

Explanation:

The optimal method to achieve maximum profit is to buy on day 2 (price = 2) and sell on day 3 (price = 6), then rebuy on day 5 (price = 0) and sell on day 6 (price = 3). The total profit would thus be (6 - 2) + (3 - 0) = 7.

Input:

The first line of input contains an integer 'T' denoting the number of test cases.

For each test case, the first line provides two space-separated integers, 'N' and 'K'.

The second line of each test case contains 'N' space-separated integers denoting the 'PRICES' array.

Output:

For each test case, output a single integer representing the maximum profit possible with at most K transactions.

Provide the result for each test case on a new line.

Constraints:

• 1 <= T <= 100
• 1 <= N <= 5000
• 0 <= K <= N/2
• 0 <= PRICES[i] <= 10⁵

Time Limit: 1 second