Longest increasing subsequence

O(n log n) patience sorting.

dp binary-search LIS

Implement `lis_length(nums: list[int]) -> int`.

Return the length of the LIS. O(n²) DP is acceptable; O(n log n) is better.

Constraints

1 ≤ len(nums) ≤ 2500

Example

>>> lis_length([10,9,2,5,3,7,101,18])
4

45 points ~40 min

Recent Submissions

No submissions yet — hit Run Tests to try!

Hints

O(n²): dp[i] = 1 + max(dp[j] for j<i if nums[j]<nums[i]).

O(n log n): maintain a 'tails' array; bisect_left for insertion point.

Test Results

Press Ctrl+Enter or click Run Tests to execute your code.