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 Ascending Count.
Re-solving the same future branches drains exponential energy.
How you win
- 1Recognize when Number of longest increasing subsequences matches the clues
- 2Keep this true after every move: length[i] and count[i] exactly summarize increasing subsequences ending at i
- 3Reach the result within O(n squared) time and O(n) space
Rules and pressure
- Target cost: O(n squared) time and O(n) space
- State rule: length[i] and count[i] exactly summarize increasing subsequences ending at i
Lesson 1 of 3
Live algorithm trace
Number of longest increasing subsequences
Complete execution1 of 6
Seed one singleton subsequence at every ending.
1
length and count start at 12
for each ending i3
for each smaller predecessor j4
if candidate length is better: replace length and count5
if equal: add predecessor count6
sum counts at global maximum lengthlengths = [1,1,1,1,1]counts = [1,1,1,1,1]
Truth to preserve / Cost target
Truth to preserve
length[i] and count[i] exactly summarize increasing subsequences ending at i
Cost target
O(n squared) time and O(n) space
Every ending stores both its best length and the number of ways to achieve that length. Better predecessors replace the count; equally good predecessors add their counts.
Your call · What should guide every step of this algorithm?