Educatifu
Open menu

Longest Increasing Subsequence

Harddynamic-programming

Find the length of the longest strictly increasing subsequence. A subsequence keeps the original order but may skip elements.

Input

Line 1: an integer n. Line 2: n integers.

Output

The length of the longest strictly increasing subsequence.

Examples

Example 1

Input
6
10 9 2 5 3 7
Output
3

The subsequence 2, 3, 7 (or 2, 5, 7) has length 3.

Example 2

Input
1
5
Output
1

A single element.

Example 3

Input
5
1 2 3 4 5
Output
5

Already increasing — length 5.

Constraints

  • 1 <= n <= 2000
  • -10^9 <= each number <= 10^9

Hints

Reveal hint 1

Let best[i] be the length of the longest increasing subsequence that ends at index i.

Reveal hint 2

best[i] = 1 + max(best[j]) over every earlier j with a[j] < a[i]; the answer is the largest best[i].

Reference solution (spoiler — try it yourself first)

Approach

O(n^2) dynamic programming: best[i] = 1 + max(best[j] : j < i and a[j] < a[i]). The answer is max(best).

import sys
d = list(map(int, sys.stdin.read().split()))
n = d[0]
a = d[1:1 + n]
best = [1] * n
ans = 1
for i in range(n):
    for j in range(i):
        if a[j] < a[i] and best[j] + 1 > best[i]:
            best[i] = best[j] + 1
    ans = max(ans, best[i])
print(ans)

← All practice problems

Bring us the problem, not a perfect specification

Tell us what needs to change, who it affects and any important deadline. We will review the context and reply with useful next questions.

  1. 01Share contextDescribe the workflow, constraint or risk.
  2. 02Clarify togetherWe identify missing facts and useful options.
  3. 03Choose a startAgree a focused assessment or delivery step.
Start a conversation