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.
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 32-bit integer.)
Next line will have n space separated integers denoting the price of stock over n days.
For each test case output one line stating the maximum profit.
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 = (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.
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!!!
you don't need DP to solve this problemLast edit: 2014-05-27 21:45:39
Please let the constraints on the price : what is the max price possible ?