Practice › Dynamic Programming
Longest Increasing Subsequence
Medium · Dynamic Programming · Asked at Amazon, Google, Microsoft, Adobe
Print the length of the longest strictly increasing subsequence.
Input
First line: n. Second line: n integers.
Output
The LIS length.
Constraints
- 1 ≤ n ≤ 10^5
- -10^9 ≤ a[i] ≤ 10^9
O(n²) DP works for small n; patience sorting with binary search gives O(n log n).
Example 1
Input
8 10 9 2 5 3 7 101 18
Output
4
Example 2
Input
4 7 7 7 7
Output
1
Hints
- O(n²): dp[i] = 1 + max(dp[j]) over j < i with a[j] < a[i]. Too slow for n = 10^5.
- Keep tails[k] = the smallest possible last value of an increasing subsequence of length k + 1. For each x, replace the first tail ≥ x (binary search), or append x.
Approach
Patience sorting. tails stays sorted. For each x, find the first index with tails[i] >= x (lower bound). If there's none, x extends the longest subsequence: append it. Otherwise set tails[i] = x, a smaller ending for subsequences of length i + 1, which leaves more room later. Using >= (not >) keeps the subsequence strictly increasing. The length of tails is the answer, though tails itself isn't necessarily a real subsequence.
Complexity: O(n log n) time · O(n) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> tails;
for (int i = 0; i < n; i++) {
long long x;
cin >> x;
auto it = lower_bound(tails.begin(), tails.end(), x);
if (it == tails.end()) tails.push_back(x);
else *it = x;
}
cout << tails.size() << "\n";
return 0;
}Python solution
import sys
from bisect import bisect_left
data = list(map(int, sys.stdin.read().split()))
tails = []
for x in data[1 : data[0] + 1]:
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = x
print(len(tails))Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] tails = new long[n];
int len = 0;
for (int i = 0; i < n; i++) {
long x = sc.nextLong();
int lo = 0, hi = len; // first tail >= x
while (lo < hi) {
int mid = (lo + hi) / 2;
if (tails[mid] >= x) hi = mid;
else lo = mid + 1;
}
tails[lo] = x;
if (lo == len) len++;
}
System.out.println(len);
}
}Solve Longest Increasing Subsequence online · All practice problems