DSA · Dynamic Programming · #102
Longest Increasing Subsequence
Module 47 · difficulty 3/5·⏱ 30:00starts on first keystroke
Given an integer array `nums`, return the length of the longest **strictly increasing subsequence**. A subsequence is a sequence derived from the array by deleting zero or more elements without changing the order of the remaining elements. Implement `lengthOfLIS(nums)`.
Examples
nums = [10,9,2,5,3,7,101,18]→4— One LIS is [2,3,7,101], length 4.nums = [0,1,0,3,2,3]→4— [0,1,2,3] is a longest increasing subsequence.nums = [7,7,7,7,7,7,7]→1— Strictly increasing, so all equal elements give length 1.
Constraints
- · 1 <= nums.length <= 2500
- · -10^4 <= nums[i] <= 10^4
- · The subsequence must be strictly increasing (no equal adjacent picks).
Session phases
A · Clarify
B · Approach
C · Complexity
D · Edges
E · Code
F · Tradeoff
G · Score
Phase A — Clarify
Ask questions about input bounds, types, and edge constraints.
Ask the coach clarifying questions about the problem.
When you've covered this phase, advance to the next.