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 Vein.
Re-solving the same future branches drains exponential energy.
How you win
- 1Recognize when Longest increasing subsequence matches the clues
- 2Keep this true after every move: dp[i] is the longest strictly increasing subsequence ending exactly 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: dp[i] is the longest strictly increasing subsequence ending exactly at i
Lesson 1 of 3
Live algorithm trace
Longest increasing subsequence
Complete execution1 of 5
Initialize every possible ending as a one-value subsequence.
1
dp[i] starts at 12
for each ending index i3
scan earlier index j4
if nums[j] < nums[i]5
dp[i] = max(dp[i], dp[j] + 1)6
return max(dp)dp = all ones
Truth to preserve / Cost target
Truth to preserve
dp[i] is the longest strictly increasing subsequence ending exactly at i
Cost target
O(n squared) time and O(n) space
For every index, find the longest increasing subsequence ending there by extending an earlier smaller value. The global answer may end anywhere.
Your call · What should guide every step of this algorithm?