Best Time to Buy and Sell Stock IV LeetCode Solution

Difficulty Level Hard
Frequently asked in Adobe Amazon Apple Bloomberg Citadel DE Shaw Facebook Goldman Sachs Google Nvidia Oracle UberViews 2963

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 ith 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.

Best Time to Buy and Sell Stock IV LeetCode Solution

Code:

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

class Solution {
public:
    int n;
    
    // dp array
    int dp[1001][2][101];
    
    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 
        if(dp[i][buy][sold]!=-1)
            return dp[i][buy][sold];
        
        // buy=true corresponds we had previously bought a stock and vice versa.
        if(buy){
            // either cosider the ith stock or move on to the next one
            return dp[i][buy][sold] = max(prices[i] + helper(i+1,not buy,k,sold+1,prices),helper(i+1,buy,k,sold,prices));
        }
        else{
            // either cosider the ith stock or move on to the next one
            return dp[i][buy][sold] = max(-prices[i] + helper(i+1,not buy,k,sold,prices),helper(i+1,buy,k,sold,prices));
        }
    }
    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)
        def helper(i,buy,sold):
            if sold>k:
                return -100000
            if i==n:
                return 0
            if (i,buy,sold) in dp:
                return dp[(i,buy,sold)]
            if buy:
                dp[(i,buy,sold)] = max(prices[i] + helper(i+1,not buy,sold+1),helper(i+1,buy,sold))
                return dp[(i,buy,sold)]
            else:
                dp[(i,buy,sold)] = max(-prices[i] + helper(i+1,not buy,sold),helper(i+1,buy,sold));
                return dp[(i,buy,sold)]
            
        return max(0,helper(0,False,0))

Complexity Analysis of Best Time to Buy and Sell Stock IV LeetCode Solution:

  • Time Complexity: The time complexity of the above code is O(nk).
  • Space Complexity: The space complexity of the above code is O(nk).
Translate »