305. Longest Increasing Subsequence

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

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

This is a classic DP problem with two approaches:

• O(n²): For each element, find the longest subsequence ending at that element
• O(n log n): Use patience sorting (binary search on tails array)

Requirements

1. Basic Functionality

• Find the length of the longest strictly increasing subsequence
• Subsequence elements maintain original relative order
• Elements don't need to be contiguous

Example Usage

lengthOfLIS([10, 9, 2, 5, 3, 7, 101, 18]);  // 4
// LIS is [2, 3, 7, 101] or [2, 5, 7, 101]

Real-World Context

• Stock analysis: Finding the longest streak of rising prices
• Version control: Finding the longest chain of compatible versions
• Task dependencies: Longest chain of ordered tasks