Best Time to Buy and Sell Stock IV

Hard
0/120
Average time to solve is 20m
profile
Contributed by
77 upvotes
Asked in companies
AdobeRazorpayOYO

Problem statement

You have been given an array 'PRICES' consisting of 'N' integers where PRICES[i] denotes the price of a given stock on the i-th day. You are also given an integer 'K' denoting the number of possible transactions you can make.

Your task is to find the maximum profit in at most K transactions. A valid transaction involves buying a stock and then selling it.

Note 
You can’t engage in multiple transactions simultaneously, i.e. you must sell the stock before rebuying it.
For Example 
Input: N = 6 , PRICES = [3, 2, 6, 5, 0, 3] and K = 2.
Output: 7

Explanation : The optimal way to get maximum profit is to buy the stock on day 2(price = 2) and sell it on day 3(price = 6) and rebuy it on day 5(price = 0) and sell it on day 6(price = 3). The maximum profit will be (6 - 2) + (3 - 0) = 7.
Detailed explanation ( Input/output format, Notes, Images )
Input Format 
The first line of input contains an integer 'T' which denotes the number of test cases or queries to be run. Then the test cases follow.

The first line of each test case contains two single-space separated integers ‘N’ and ‘K’, respectively.

The second line of each test case contains ‘N’ single space-separated integers, denoting the elements of the array 'PRICES'.
Output Format 
For each test case, print a single integer denoting the maximum profit in at most K transactions.

Print the output of each test case in a separate line.
Note 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints 
1 <= T <= 100
1 <= N <= 5000
0 <= K <= N/2
0 <= ARR[i] <=10^5

Time Limit : 1 sec
Sample Input 1
2
5 2
8 5 1 3 10
4 2
10 8 6 2
Sample Output 1
9
0
Explanation for Sample 1
Test Case 1: In this case, we can make a maximum of 2 transactions. The optimal way to get maximum profit is to make only 1 transaction, i.e., buy the stock on day 3 (price = 1) and sell it on day 5(price = 10). The profit will be 10 - 1 = 9.

Test Case 2: In the second test case, we can make a maximum of 2 transactions. The optimal way to get maximum profit is to make 0 transactions because the price of stock is continuously decreasing and we will have a loss if we buy and sell the stock.
Sample Input 2
2
4 0
2 6 5 2
4 2
1 2 3 5
Sample Output 2
0
4
Hint

Can you come up with a recurrence relation?

Approaches (3)
Recursion

The main idea is to use recursion to reduce the big problem into several smaller subproblems.

 

Algorithm

 

  • We will call a maxProfit function that returns us the maximum profit we can get from the array starting from i (here i denotes the starting index of PRICES) to N - 1. We will use a bool variable buy. If buy == true it denotes that we had bought a stock and now we can’t buy another until we sell it and buy == false denotes that we hadn’t currently bought any stock. The maxProfit function will work as follows:

 

  • If K == 0 || i == N
    • Return 0.
  • If buy == false
    • We make a recursive call to i + 1 with buy marked as false. (Not holding the stock).
    • We make a recursive call to i + 1 with buy marked as true and subtract PRICES[i]. (Buy stock on i -th day).
    • We finally return the maximum of them.
  • Else
    • We make a recursive call to i + 1 with buy marked as true. (Hold the stock).
    • We make a recursive call to i + 1 with buy marked as false and add PRICES[i] and decrement K by 1. (Sell stock on i-th day).
    • Return the maximum of them.
Time Complexity

O(2 ^ N), where ‘N’ denotes the number of elements in an array. 

 

In the worst case at every step, we are making two recursive calls and the maximum depth of the recursion tree can go up to N. Hence the time complexity is O(2 ^ N).

Space Complexity

O(N), where ‘N’ denotes the number of elements in an array.

 

In the worst case, extra space is used by the recursion stack which can go up to a maximum depth of N. Hence the space complexity is O(N). 

Code Solution
(100% EXP penalty)
Best Time to Buy and Sell Stock IV
Full screen
Console