STK  Stock
Alex heard a lot about investing in the stock market and now wants to do it to earn some profit. Being a new investor he is scared of the risks in the stock market, so he decides that at any instance he will not have more than one stock with him. It is also decided that on a particular day he can either buy or sell atmost one stock(only one transaction allowed). Now given the prices of one particular stock over the period of n days Alex decides he will make atmost k buys and k sells.
Write a code to help Alex to maximize his profit.
Input
First line contains an integer T(<=100), number of test cases.
Each test case will have n(<=3000) and k(1<=k<=n/2), is the no. of days and the maximum buys/sells allowed respectively.
(Value of the prices are in range of unsigned 32bit integer.)
Next line will have n space separated integers denoting the price of stock over n days.
Output
For each test case output one line stating the maximum profit.
Example
Sample Input: 3 10 3 2 7 3 9 8 7 9 7 1 9 10 1 2 7 3 9 8 7 9 7 1 3 10 2 2 7 3 9 8 7 9 7 1 9 Sample Output: 19 7 15 Explanation: 1st test case Alex would buy on 1st day and sell it on the 2nd day, and then buy another on the 3rd day and sell it on the 4th, finally buys on 9th day and sells on the 10th day.So profit = (72)+(93)+(91) = 19. 2nd test case Alex would buy on 1st day and sell it on the 4th(or 7th) day. So profit = 92 = 7. 2nd test case Alex would buy on 1st day and sell it on the 4th day, and then buy another on the 9th day and sell it on the 10th day.So profit = (92)+(91) = 15.
hide comments
Tensor:
20150312 20:35:30
I wrote the code not considering (K) and get accepted ?!!!!!, test cases are wrong it gives me 21, 15, 21 and my code get accepted, please fix the test data or the problem at all!!! 

Andy:
20140527 21:34:57
you don't need DP to solve this problem Last edit: 20140527 21:45:39 

Francky:
20140405 12:18:14
Please let the constraints on the price : what is the max price possible ?

Added by:  Abhra 
Date:  20140405 
Time limit:  5s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: ASM64 