Longest Increasing Subsequence (LIS)

Solve LIS with O(n\u00b2) DP approach and the optimal O(n log n) patience sorting algorithm, with complete analysis and code.

The Problem

Given an array of integers, find the length of the longest subsequence where each element is strictly greater than the previous one. Elements do not need to be contiguous.

Example: [10, 9, 2, 5, 3, 7, 101, 18]

LIS: [2, 3, 7, 101] or [2, 5, 7, 101] — length 4
NOT [2, 3, 7, 18, 101] because 18 comes before 101 in the array but we cannot rearrange

Approach 1: O(n²) Dynamic Programming

State: dp[i] = length of the longest increasing subsequence ending at index i

Transition: For each j < i where nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) — extend the best subsequence ending at j

Base: dp[i] = 1 for all i (each element alone is a subsequence of length 1)

Answer: max(dp[i]) for all i

Dry Run

dp[3] = 2 (nums[2]=2 < nums[3]=5	dp[2]+1=2) → [2, 5]
dp[4] = 2 (nums[2]=2 < nums[4]=3	dp[2]+1=2) → [2, 3]
dp[5] = 3 (nums[3]=5 < nums[5]=7	dp[3]+1=3) → [2, 5, 7]
(nums[4]=3 < nums[5]=7	dp[4]+1=3) → [2, 3, 7]
dp[6] = 4 (nums[5]=7 < nums[6]=101	dp[5]+1=4) → [2, 5, 7, 101]
dp[7] = 4 (nums[5]=7 < nums[7]=18	dp[5]+1=4) → [2, 5, 7, 18]
Answer	max(dp) = 4

Python Implementation

Example

def lis_dp(nums): if not nums: return 0 n = len(nums) dp = [1] * n for i in range(1, n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) # To find the actual subsequence: def lis_with_sequence(nums): n = len(nums) dp = [1] * n parent = [-1] * n for i in range(1, n): for j in range(i): if nums[j] < nums[i] and dp[j] + 1 > dp[i]: dp[i] = dp[j] + 1 parent[i] = j # Find the index of the maximum max_idx = dp.index(max(dp)) # Reconstruct seq = [] while max_idx != -1: seq.append(nums[max_idx]) max_idx = parent[max_idx] return seq[::-1] print(lis_with_sequence([10, 9, 2, 5, 3, 7, 101, 18])) # [2, 5, 7, 101] or [2, 3, 7, 101]

Time: O(n²), Space: O(n)

Approach 2: O(n log n) with Patience Sorting

The O(n²) approach is too slow for large inputs (n > 10,000). The optimal approach uses an idea from the card game "Patience" (solitaire):

Key insight: Maintain an array tails where tails[i] is the smallest possible tail element for an increasing subsequence of length i+1.

Algorithm:

For each number in the array:
If it is larger than all elements in tails, append it (extends longest subsequence)
Otherwise, replace the first element in tails that is ≥ current number (binary search)
The length of tails is the LIS length

Why This Works

tails always stays sorted. By keeping the smallest possible tail for each length, we maximize the chance of extending the subsequence later. Replacing a larger tail with a smaller one does not affect current LIS length but opens up future possibilities.

Dry Run

Process 10	tails = [10] (append, new longest = 1)
Process 9	tails = [9] (replace 10 with 9)
Process 2	tails = [2] (replace 9 with 2)
Process 5	tails = [2, 5] (append, longest = 2)
Process 3	tails = [2, 3] (replace 5 with 3)
Process 7	tails = [2, 3, 7] (append, longest = 3)
Process 101	tails = [2, 3, 7, 101] (append, longest = 4)
Process 18	tails = [2, 3, 7, 18] (replace 101 with 18)
Answer	len(tails) = 4

Note: tails is NOT the actual LIS! It is a helper array. [2, 3, 7, 18] happens to be a valid LIS here, but that is not always the case.

Python Implementation

Example

import bisect def lis_optimal(nums): """O(n log n) LIS using binary search.""" tails = [] for num in nums: pos = bisect.bisect_left(tails, num) if pos == len(tails): tails.append(num) # Extends longest subsequence else: tails[pos] = num # Replace with smaller tail return len(tails) print(lis_optimal([10, 9, 2, 5, 3, 7, 101, 18])) # 4

C++ Implementation

cpp example

#include <vector>
#include <algorithm>
using namespace std;

int lisOptimal(vector<int>& nums) {
    vector<int> tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end())
            tails.push_back(num);
        else
            *it = num;
    }
    return tails.size();
}

Time: O(n log n) — n elements, binary search O(log n) each Space: O(n) — for the tails array

Recovering the Actual LIS in O(n log n)

Example

import bisect def lis_with_recovery(nums): n = len(nums) tails = [] indices = [] # indices[i] = index in nums of tails[i] parent = [-1] * n for i, num in enumerate(nums): pos = bisect.bisect_left(tails, num) if pos == len(tails): tails.append(num) indices.append(i) else: tails[pos] = num indices[pos] = i parent[i] = indices[pos - 1] if pos > 0 else -1 # Reconstruct from the last element seq = [] idx = indices[len(tails) - 1] while idx != -1: seq.append(nums[idx]) idx = parent[idx] return seq[::-1]

Comparison

Approach	Time	Space	Recovers sequence?
O(n²) DP	O(n²)	O(n)	Yes (with parent array)
Patience sort	O(n log n)	O(n)	Yes (with extra tracking)

Variations

Non-decreasing: Use bisect_right instead of bisect_left
Longest Decreasing: Negate all elements, find LIS
Number of LIS: Track count alongside length in O(n²) approach
Minimum number of increasing subsequences to cover array: Equals length of Longest Non-Increasing Subsequence (Dilworth's theorem)

Applications

Stock analysis: Longest run of increasing prices
Patience sorting: Actually sorts using O(n log n) comparisons
Scheduling: Longest chain of compatible tasks
Computational geometry: Longest chain of points (sorted by x, LIS on y)

The Problem

Given an array of integers, find the length of the longest subsequence where each element is strictly greater than the previous one. Elements do not need to be contiguous.

Example: [10, 9, 2, 5, 3, 7, 101, 18]

LIS: [2, 3, 7, 101] or [2, 5, 7, 101] — length 4
NOT [2, 3, 7, 18, 101] because 18 comes before 101 in the array but we cannot rearrange

Approach 1: O(n²) Dynamic Programming

State: dp[i] = length of the longest increasing subsequence ending at index i

Transition: For each j < i where nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) — extend the best subsequence ending at j

Base: dp[i] = 1 for all i (each element alone is a subsequence of length 1)

Answer: max(dp[i]) for all i

Dry Run

dp[3] = 2 (nums[2]=2 < nums[3]=5	dp[2]+1=2) → [2, 5]
dp[4] = 2 (nums[2]=2 < nums[4]=3	dp[2]+1=2) → [2, 3]
dp[5] = 3 (nums[3]=5 < nums[5]=7	dp[3]+1=3) → [2, 5, 7]
(nums[4]=3 < nums[5]=7	dp[4]+1=3) → [2, 3, 7]
dp[6] = 4 (nums[5]=7 < nums[6]=101	dp[5]+1=4) → [2, 5, 7, 101]
dp[7] = 4 (nums[5]=7 < nums[7]=18	dp[5]+1=4) → [2, 5, 7, 18]
Answer	max(dp) = 4

Python Implementation

Example

Time: O(n²), Space: O(n)

Approach 2: O(n log n) with Patience Sorting

The O(n²) approach is too slow for large inputs (n > 10,000). The optimal approach uses an idea from the card game "Patience" (solitaire):

Key insight: Maintain an array tails where tails[i] is the smallest possible tail element for an increasing subsequence of length i+1.

Algorithm:

For each number in the array:
If it is larger than all elements in tails, append it (extends longest subsequence)
Otherwise, replace the first element in tails that is ≥ current number (binary search)
The length of tails is the LIS length

Why This Works

Dry Run

Process 10	tails = [10] (append, new longest = 1)
Process 9	tails = [9] (replace 10 with 9)
Process 2	tails = [2] (replace 9 with 2)
Process 5	tails = [2, 5] (append, longest = 2)
Process 3	tails = [2, 3] (replace 5 with 3)
Process 7	tails = [2, 3, 7] (append, longest = 3)
Process 101	tails = [2, 3, 7, 101] (append, longest = 4)
Process 18	tails = [2, 3, 7, 18] (replace 101 with 18)
Answer	len(tails) = 4

Note: tails is NOT the actual LIS! It is a helper array. [2, 3, 7, 18] happens to be a valid LIS here, but that is not always the case.

Python Implementation

Example

C++ Implementation

cpp example

#include <vector>
#include <algorithm>
using namespace std;

int lisOptimal(vector<int>& nums) {
    vector<int> tails;
    
    for (int num : nums) {
        auto it = lower_bound(tails.begin(), tails.end(), num);
        if (it == tails.end())
            tails.push_back(num);
        else
            *it = num;
    }
    return tails.size();
}

Time: O(n log n) — n elements, binary search O(log n) each Space: O(n) — for the tails array

Recovering the Actual LIS in O(n log n)

Example

Comparison

Approach	Time	Space	Recovers sequence?
O(n²) DP	O(n²)	O(n)	Yes (with parent array)
Patience sort	O(n log n)	O(n)	Yes (with extra tracking)

Variations

Non-decreasing: Use bisect_right instead of bisect_left
Longest Decreasing: Negate all elements, find LIS
Number of LIS: Track count alongside length in O(n²) approach
Minimum number of increasing subsequences to cover array: Equals length of Longest Non-Increasing Subsequence (Dilworth's theorem)

Applications

Stock analysis: Longest run of increasing prices
Patience sorting: Actually sorts using O(n log n) comparisons
Scheduling: Longest chain of compatible tasks
Computational geometry: Longest chain of points (sorted by x, LIS on y)

Longest Increasing Subsequence (LIS)

The Problem

Approach 1: O(n²) Dynamic Programming

Dry Run

Python Implementation

Approach 2: O(n log n) with Patience Sorting

Why This Works

Dry Run

Python Implementation

C++ Implementation

Recovering the Actual LIS in O(n log n)

Comparison

Variations

Applications

Continue learning this concept

Longest Increasing Subsequence (LIS)

The Problem

Approach 1: O(n²) Dynamic Programming

Dry Run

Python Implementation

Approach 2: O(n log n) with Patience Sorting

Why This Works

Dry Run

Python Implementation

C++ Implementation

Recovering the Actual LIS in O(n log n)

Comparison

Variations

Applications

Continue learning this concept