Greedy Algorithms - Best Time to Buy and Sell Stock II
Given the final profit output of 7 from the peak-valley approach on an unknown price array of length 6, which of the following could be the original prices?
Given the final profit output of 7 from the peak-valley approach on an unknown price array of length 6, which of the following could be the original prices?
hard🔄 Reverse Engineer Q9 of Q15
Step-by-Step Solution
Solution:
Step 1: Analyze profit for each option
[7, 6, 5, 4, 3, 2] is strictly decreasing -> profit 0; [1, 2, 3, 4, 5, 6] strictly increasing -> profit 5; [5, 5, 5, 5, 5, 5] constant -> profit 0.Step 2: Match profit 7
Only [7, 1, 5, 3, 6, 4] matches known example with profit 7.Final Answer:
Option A -> Option AQuick Check:
Profit 7 matches known input [OK]
Quick Trick: Profit 7 matches known example prices [OK]
Common Mistakes:
MISTAKES- Assuming increasing array yields max profit
- Ignoring constant price arrays
- Confusing profit calculation
Trap Explanation:
PITFALL- Candidates pick increasing prices expecting max profit but miss sum of multiple peaks.
Interviewer Note:
CONTEXT- Tests reverse reasoning from output to input.
Master "Best Time to Buy and Sell Stock II" in Greedy Algorithms
Want More Practice?
15+ quiz questions · All difficulty levels · Free
Free Signup - Practice All QuestionsMore Greedy Algorithms Quizzes