Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing subsequence.

A subsequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the relative order of the remaining characters.

• For example, "cat" is a subsequence of "crabt".

The longest increasing subsequence is [1,2,3,7], which has a length of 4.

Approach

Use patience sorting with a tails array. For each number, binary search the leftmost position in tails it can replace (first value >= num). If it is larger than all tails, append it. The length of tails is the LIS length.

Why It Works

tails[i] stores the smallest possible tail value for an increasing subsequence of length i + 1. Replacing with a smaller tail keeps future options open without reducing subsequence lengths. Therefore the final size of tails equals the LIS length.

Complexity

• Time: O(n log n)
• Space: O(n)

Reference Implementation (Python)

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        tails = []
        for num in nums:
            idx = bisect.bisect_left(tails, num)
            if idx == len(tails):
                tails.append(num)
            else:
                tails[idx] = num
        return len(tails)