What is the length of the longest increasing subsequence?
Given an array of integers, choose numbers in their original order so that every next number is strictly larger. You may skip elements, but you cannot rearrange them. Find the greatest possible length.
A question to try first
The intuition
At each number, take it or skip it.
A recursive state solve(i, previous_index) asks: “What is the best length from index i onward, given the last number I chose?” Taking nums[i] is allowed only when it is larger than the previous choice.
Memoization makes this intuitive approach O(n²) time and O(n²) space, because there are roughly n choices for the current index and n choices for the previous index.
The faster idea
Keep only the best ending.
tails[k] is the smallest possible ending value for an increasing subsequence of length k + 1 seen so far.
A smaller ending is better: it leaves more room for future values. Since tails stays sorted, binary search finds the position in O(log n).
Interactive walkthrough
Watch tails evolve
Step through every comparison, then see the append or replacement.
Input array · original order
Smallest ending for each length · tails
Find the first tail ≥ x
Use lower_bound(tails, x). This is the first slot whose current ending is at least the new number. Equality matters: equal values cannot extend a strictly increasing subsequence.
Append or replace
If the position equals len(tails), append x: we found a longer subsequence. Otherwise replace that slot with x: we improved an ending without increasing the length.
Return the length
Each slot represents one achievable length, so the answer is len(tails). Across all n values, each binary search takes O(log n).
Why replacing helps
A smaller tail keeps options open.
Suppose tails = [4, 10] and the next value is 5. Replacing 10 with 5 preserves a length-2 subsequence while making it easier to extend. A future 8 can follow 5, even though it could not follow 10.
The important subtlety
tails is not necessarily an LIS.
For [4, 10, 5, 8, 3, 9], the final tails array is [3, 5, 8, 9]. But 3 appears after 5 and 8 in the input, so that array is not a valid subsequence. Its length 4 is still correct; one actual LIS is [4, 5, 8, 9].
Read each slot as an independent best ending for its length, not as a path through the original array.
Python reference
The two perspectives in code
Start with the recursive decision. Then use the binary-search version when you need the optimized length.
from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
def lower_bound(tails, target):
left, right = 0, len(tails) - 1
while left <= right:
mid = left + (right - left) // 2
if tails[mid] >= target:
right = mid - 1
else:
left = mid + 1
return left
tails = []
for num in nums:
pos = lower_bound(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num
return len(tails)from typing import List
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
n = len(nums)
dp = {}
def solve(i, previous_index):
if i == n:
return 0
if (i, previous_index) in dp:
return dp[(i, previous_index)]
not_take = solve(i + 1, previous_index)
take = 0
if previous_index == -1 or nums[i] > nums[previous_index]:
take = 1 + solve(i + 1, i)
dp[(i, previous_index)] = max(take, not_take)
return dp[(i, previous_index)]
return solve(0, -1)Both return 0 for an empty array. The animation follows the binary-search code exactly, including its inclusive left and right bounds.