Typical example
Input
nums = [10, 9, 2, 5, 3, 7, 101, 18]
Output
4
One LIS is [2, 3, 7, 101], which has length 4.
Full lesson preview
Find the longest increasing subsequence
Compute the length of the longest strictly increasing subsequence in an array of integers.
Python practice32 minDynamic ProgrammingAdvancedLast updated March 29, 2026
Problem statement
Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is derived by deleting some or no elements without changing the order of the remaining elements. The subsequence must be strictly increasing.
Aim to implement an algorithm that runs in O(n log n) time using a tails array and binary search.
Task
Implement an efficient algorithm (O(n log n)) for the Longest Increasing Subsequence (LIS) using patience sorting technique and binary search.
Examples
Input format
Function lis_length(nums) where nums is a list of integers.
Output format
Return an integer representing the length of the longest strictly increasing subsequence.
Constraints
0 <= len(nums) <= 10^5, -10^9 <= nums[i] <= 10^9. Aim for O(n log n) time and O(n) space.
Samples
Sample 1
Input
nums = [3, 10, 2, 1, 20]
Output
3
A LIS is [3, 10, 20] of length 3.