Problem context and objectives
Mission briefing
Energy-route planner · A runner crosses a line of power stations
Build each decision from smaller outcomes already solved: The Product Polarity.
Re-solving the same future branches drains exponential energy.
How you win
- 1Recognize when Maximum product subarray matches the clues
- 2Keep this true after every move: maxEnd and minEnd are the extreme products of subarrays ending at the current index
- 3Reach the result within O(n) time and O(1) space
Rules and pressure
- Target cost: O(n) time and O(1) space
- State rule: maxEnd and minEnd are the extreme products of subarrays ending at the current index
Lesson 1 of 3
Live algorithm trace
Maximum product subarray
Complete execution1 of 5
Initialize both ending extremes to the first value.
1
maxEnd = minEnd = first value2
for each next value3
compute value, value*oldMax, value*oldMin4
maxEnd = maximum candidate5
minEnd = minimum candidate6
update and return global maximummaxEnd = 2minEnd = 2answer = 2
Truth to preserve / Cost target
Truth to preserve
maxEnd and minEnd are the extreme products of subarrays ending at the current index
Cost target
O(n) time and O(1) space
A negative value swaps the roles of the largest and smallest ending products. Track both extremes, plus the option to restart at the current value.
Your call · What should guide every step of this algorithm?