Best Time to Buy and Sell Stock IV
Recognize the pattern
Brute force idea
If you approach Best Time to Buy and Sell Stock IV in the most literal way possible, you get this: Try all possible k-transaction combinations. Each transaction pair is chosen independently. It is a fair place to begin because it matches the surface of the question, yet it does not capture the deeper structure that makes the problem simpler.
Better approach
The deeper shift in Best Time to Buy and Sell Stock IV is this: 3D DP: dp[t][i] = max profit using at most t transactions up to day i. dp[t][i] = max(dp[t][i-1], max over j<i of (prices[i] - prices[j] + dp[t-1][j-1])). Optimize inner max to with running maximum. Once you hold onto the right piece of information from moment to moment, the problem feels less like trial and error and more like following a shape that was there all along.
Key invariant
At the center of Best Time to Buy and Sell Stock IV is one steady idea: At each day, you either do nothing or complete a transaction's sell. The running maximum trick avoids re-scanning: maxDiff = max(maxDiff, dp[t-1][j-1] - prices[j]), then dp[t][i] = max(dp[t][i-1], prices[i] + maxDiff). When you keep that truth intact, each local choice supports the larger solution instead of fighting it.
Watch out for
The trap in Best Time to Buy and Sell Stock IV usually looks like this: Not handling the case where k ≥ n/2 — with enough transactions, you can capture every profit, reducing to the unlimited transactions problem (much simpler greedy). When the code becomes mechanical before the idea is clear, small edge cases start breaking the whole story.