# Best Time to Buy and Sell Stock IV LeetCode Solution

Difficulty Level Hard

## Problem Statement:

Best Time to Buy and Sell Stock IV LeetCode Solution: You are given an integer array `prices` where `prices[i]` is the price of a given stock on the `i`th day, and an integer `k`.

Find the maximum profit you can achieve. You may complete at most `k` transactions.

Note: You may not engage in multiple transactions simultaneously (i.e., you must sell the stock before you buy again).

## Examples:

Example 1:

Input:

``` k = 2, prices = [2,4,1]
```

Output:

``` 2
```

Explanation:

``` Buy on day 1 (price = 2) and sell on day 2 (price = 4), profit = 4-2 = 2.
```

Example 2:

Input:

``` k = 2, prices = [3,2,6,5,0,3]
```

Output:

``` 7
```

Explanation:

` Buy on day 2 (price = 2) and sell on day 3 (price = 6), profit = 6-2 = 4. Then buy on day 5 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.`

## Approach:

### Idea:

We will be solving the problem with the concept of dynamic programming. First, we can generate the recursive solution and then can optimize it using memoization. First, we will check for the base case and then will tell the function when to return. Here the base conditions are:

1. When we reach the last index of the prices array.
2. When the number of transactions becomes greater than k.

Coming to the logic part. In any given situation we will be having 2 cases.

1. If previously we bought a stock for some value, then for the current index i, either we can sell the previously bought stock for this price or we can simply move on to the next index i.e., i+1.
2. If we haven’t bought any stock previously, then for the current index i, either we can buy this ith stock, costing us prices[i] or we can simply move on i+1th index.

In the end, we will be returning the max value from either of the 2 cases. We will use a buy flag to keep track of whether currently, we need to buy a stock or need to sell a stock. Check out the code for a better understanding. ### Code:

Best Time to Buy and Sell Stock IV C++ Solution:

```class Solution {
public:
int n;

// dp array
int dp;

int helper(int i,bool buy,int k,int sold,vector<int>& prices){
// Base cases
if(sold>k)
return -100000;
if(i==n){
return 0;
}

// check if the value already existed

// buy=true corresponds we had previously bought a stock and vice versa.
// either cosider the ith stock or move on to the next one
}
else{
// either cosider the ith stock or move on to the next one
}
}
int maxProfit(int k, vector<int>& prices) {
memset(dp,-1,sizeof(dp));
n = prices.size();
return max(0,helper(0,0,k,0,prices));
}
};```

Best Time to Buy and Sell Stock IV Python Solution:

```class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
dp = {}
n = len(prices)
if sold>k:
return -100000
if i==n:
return 0