Find the longest increasing subsequence length
Find the length of the longest strictly increasing subsequence in an integer array.
Course progress
Problem 93 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
numbers = [10, 9, 2, 5, 3, 7, 101, 18]
Expected output
4
What is happening?
One longest increasing subsequence is 2, 3, 7, 101. It contains four values; no increasing subsequence contains five.
Solution strategy
Build the right mental model
Maintain the smallest possible ending value for every subsequence length and replace the first ending value not smaller than each input.
Core concepts
binary search · dynamic programming
Complexity
Time O(n log n), space O(n).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for longest-increasing-subsequence
using System;
class Program
{
static int LongestIncreasingSubsequence(int[] numbers)
{
int[] tails = new int[numbers.Length];
int length = 0;
foreach (int number in numbers)
{
int low = 0, high = length;
while (low < high)
{
int middle = low + (high - low) / 2;
if (tails[middle] < number) low = middle + 1;
else high = middle;
}
tails[low] = number;
if (low == length) length++;
}
return length;
}
static void Main()
{
Console.WriteLine(LongestIncreasingSubsequence(
new[] { 10, 9, 2, 5, 3, 7, 101, 18 }));
}
}Knowledge check
Questions students often ask
What is the main idea behind find the longest increasing subsequence length?
Maintain the smallest possible ending value for every subsequence length and replace the first ending value not smaller than each input.
What is the time and space complexity of this solution?
Time O(n log n), space O(n).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.