# Best Time To Buy and Sell Stock

#### 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.
```

##### 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
```

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

Algorithm

- We will call a
function that returns us the maximum profit we can get from the array starting from**maxProfit***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.

- We make a recursive call to
- 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 - Return the maximum of them.

- We make a recursive call to

If we draw the recursion tree for the recurrence relation of approach 1, we can observe that there are a lot of overlapping subproblems. There are only *N * K * distinct recursive calls.

Lets understand this by an example, consider PRICES = [5, 4, 8, 9] and *K *= 3 and *buy* == false.

The recursion tree for array will be

As we can clearly see in the recursion tree that [8, 9] for *K == 3* and *buy == true *will be calculated twice.

Since the problem has overlapping subproblems, we can solve it more efficiently using memorization.

The algorithm is similar to the previous approach with some additions.

We initialize a 3-D vector *memo* with -1. Now, *memo[i][j][0]* will denote the maximum profit we can get from the array starting from ‘*i’ *to *N* - 1 in at most ‘*j*’ transactions considering currently we haven't bought the stock. *memo[i][j][1] *will denote the maximum profit we can get from the array starting from ‘*i*’ to *N* - 1 in at most ‘*j*’ transactions considering currently we have bought the stock.

Before calling the function for any valid (*i, j, buy*), we will check whether we already have a solution corresponding to the *(i, j, m*) present in *memo*.

- If we already have a solution corresponding to (
*i, j, m*), we return the solution. - Else
- If
*buy*== 0- We call the recursive function for (
*i + 1, j, 0*) and*(i + 1, j, 1*) -*PRICES[i]*and store the maximum of them in*memo[i][j][buy]*and return it.

- We call the recursive function for (
- Else if
*buy*== 1- We call the recursive function for (
*i + 1, j, 1*) and*(i + 1, j - 1, 0*) +*PRICES[i]*and store the maximum of them in*memo[i][j][buy]*and return it.

- We call the recursive function for (

- If

Initially, we were breaking the large problem into small subproblems but now, let us look at it differently. The idea is to solve the small problem first and then reach the final answer. Thus we will be using a bottom-up approach now.

We initialize two 2-D matrices,* buy[K+1][N+1] *and* sell[K+1][N+1]. *Here,* buy[i][j]* will denote the maximum profit we can get in at most ‘*i*’ transactions from the array starting from index* 0* and ending at index* j -1* and the final state is buying the stock. *sell[i][j]* will denote the maximum profit we can get in at most ‘*i*’ transactions from the array starting from index 0 and ending at index* j -1* and the final state is not holding the stock i.e. selling the stock.

Algorithm

- We iterate the matrix
*buy*and*sell*column-wise and update the values.*buy[j][i] = max(buy[j][i-1], sell[j-1][i-1] - PRICES[i-1])*. Here*buy[j][j-1]*denotes holding the stock and*sell[j -1][i - 1] - PRICES[i -1]*denotes buying the stock on*i-th*day.*sell[j][i] = max(sell[j][i-1], buy[j][i-1]+PRICES[i-1])*. Here*sell[j][i-1]*denotes not holding the stock and*buy[i][j - 1] + PRICES[i -1]*denotes selling the stock on*i-th*day.

- Finally return
*sell[K][N].*