188. Best Time to Buy and Sell Stock IV

Leetcode

📝 Problem Details

• Title: 188. Best Time to Buy and Sell Stock IV
• Link: https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/
• Difficulty: Hard
• Tags/Categories: Greedy Dynamic-Programming

💭What Were My Initial Thoughts?

- a brute force solution would involve exploring all possible combinations of at most k transactions and computing profit for each
- this is highly inefficient with a TC of O(2^n) exponential time 

🤔What Did I Struggle With?

- implementing the brute force
- thinking of a better solution compared to the brute force approach
- dynamic programming implementation

💡 Explanation of Solution

1. Transaction definition: A transaction consists of ony buy and one sell, and you can make at most k transactions

2. Special Case for Large k : if k is greater than or equal to half the number of days, you can trade as much as you want, simplifying the problem to capturing all upward price movements

3. Dynamic Programming for Limited k: when k is small, use dynamic programming to compute the maximum profit
	- track the best profit with up to i transactions by day j
	- decide whether to do nothing or sell on day j based on the best previous buy

⌛ Complexity Analysis

💻 Implementation of Solution

class Solution {
public:
	int maxProfit(int k, vector<int>& prices) {
		int n = prices.size();
		int maxProfit = 0;
		
		if(n <= 0) return 0;
	
		// if k is very large, reduce to unlimited transactions
		if( k >= n / 2) {
			for(int i = 1; i < n; i++) {
				if(prices[i] > prices[i-1])
					maxProfit += prices[i] - prices[i-1];
			}	
			return maxProfit;
		}
 
		// dp table to track the maximum profit
		vector<vector<int>> dp(k+1, vector<int>(n,0));
 
		for(int i=1; i <= k; i++) { // why is the starting index at 1
			int maxDiff = -prices[0]; //what does -prices do
			
			for(int j=1; j < n; j++) {
				dp[i][j] = max(dp[i][j - 1], prices[j] + maxDiff); 
				maxDiff = max(maxDiff, dp[i - 1][j] - prices[j]);
			}
		}
		return dp[k][n-1];
	}
};