LeetMotion
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is an array derived from another array by deleting some or no elements without changing the order of the remaining elements.
dp[i] = the length of the longest increasing subsequence that ends at index i. Every element starts a subsequence of length 1 by itself, so dp[i] = 1 initially. The final answer is max(dp) — not just dp[n-1], because the LIS can end anywhere.j < i, if nums[j] < nums[i], then we can extend the LIS ending at j by appending nums[i]. So the recurrence is:dp[i] = max(dp[i], 1 + dp[j]) for all j < i where nums[j] < nums[i].tails where tails[i] is the smallest tail of any IS of length i+1. For each number, binary search for where it fits and replace or extend. The length of tails at the end is the LIS length. The DP approach here visualizes the core recurrence intuitively before reaching for the optimized solution.Imagine you're stacking boxes left to right on a shelf — you can only place a box on a stack if it's taller than all boxes below it. dp[i] is the tallest stack you can build using box i as the top. For each box i, you look back at every earlier box j: if box j is shorter than box i, you can put box i on top of j's stack. The best stack ending at i is 1 + max(dp[j]) for all valid j. The answer is the tallest stack among all positions.
Define dp[i] as the length of the longest strictly increasing subsequence that ends at index i. Initialize all to 1. For each i, scan all previous indices j < i: if nums[j] < nums[i], update dp[i] = max(dp[i], 1 + dp[j]). The answer is max(dp).
dp = [1] * n — each element alone is a subsequence of length 1.i from 0 to n−1: nums[i] is the candidate tail of the subsequence.j from 0 to i−1: if nums[j] < nums[i], we can extend the LIS ending at j. Update dp[i] = max(dp[i], 1 + dp[j]).max(dp).
Discussion
…