Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. O(n²): dp[i] = 1 + max(dp[j]) over j < i with a[j] < a[i]. Too slow for n = 10^5.
  2. 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