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 at most 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 at most 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 number of days and the maximum buys/sells allowed respectively.
(Value of the prices are in range of unsigned 32-bit 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
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 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 = (7-2)+(9-3)+(9-1) = 19.
2nd test case Alex would buy on 1st day and sell it on the 4th(or 7th) day. So profit = 9-2 = 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 = (9-2)+(9-1) = 15.
hide comments
Simes:
2021-05-11 21:56:43
@Tensor - that's still true. My incorrect solution gives the same answers as yours but also got AC. |
|
Tensor:
2015-03-12 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:
2014-05-27 21:34:57
you don't need DP to solve this problem Last edit: 2014-05-27 21:45:39 |
|
Francky:
2014-04-05 12:18:14
Please let the constraints on the price : what is the max price possible ?
|
Added by: | Abhra |
Date: | 2014-04-05 |
Time limit: | 5s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |