Stonks :
Difficulty Level : Hard
Submissions : 142
Asked In :
Marks :20
: 1 | : 0
You are given an integer array $$$prices$$$ where $$$prices[i]$$$ is the price of a given stock on the $$$i^{th}$$$ day for subsequent $$$n$$$ days, and an integer $$$k$$$.
Find the maximum profit you can achieve. You may complete at most $$$k$$$ transactions.
Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).
The first line of input contains an integer $$$t$$$ $$$(1 \le t \le 100)$$$ — the number of testcases.
The first line of each testcase contains two space separated integers $$$n$$$ and $$$k$$$ $$$(1 \le k \le n \le 1000)$$$ — the number of days and the maximum number of transactions that you can perform.
The second line of each testcase contains $$$n$$$ space separated integers $$$prices[1], prices[2]... prices[n]$$$ $$$(0 \le prices[i] \le 10^{15})$$$ — the elements of the $$$prices$$$ array respectively.
It is guaranteed that the individual sums of $$$n$$$ and $$$k$$$ over all testcases does not exceed $$$1000$$$.
For each test case, print a single integer — the maximum profit you can obtain in a single new line.
3 3 2 2 4 1 6 2 3 2 6 5 0 3 6 2 5 20 10 30 50 70
2 7 75
In sample test case 1, Buy on day $$$1$$$ $$$(price = 2)$$$ and sell on day $$$2$$$ $$$(price = 4)$$$, profit $$$= 4-2 = 2$$$.
In sample test case 2, 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$$$. Hence total profit $$$ = 4 + 3 = 7.$$$
