Longest Increasing Subsequence

Interview

Time limit1sMemory limit256 MB

Summary

Find the length of the longest strictly increasing subsequence of the given sequence.

Level: Medium4 of 10
Topics: Dynamic programming, Binary search
Solved: No attempts yet

Problem

Given a sequence $A$ , write a program that finds the length of its longest increasing subsequence.

A subsequence of $A$ is what remains after deleting zero or more elements and keeping the rest in their original order. An increasing subsequence is one whose values grow strictly from left to right, so two elements with the same value cannot both be chosen.

For example, when $A = (10, 20, 10, 30, 20, 50)$ , the longest increasing subsequence is 10, 20, 30, 50, and its length is 4.

Input

The first line contains the size $N$ of the sequence $A$ ( $1 \le N \le 1000$ ).

The second line contains $A_1, A_2, \dots, A_N$ , separated by spaces ( $1 \le A_i \le 1000$ ).

Output

Print the length of the longest increasing subsequence of $A$ on the first line.

Examples5

Example 1
Input
```
6
10 20 10 30 20 50
```
Expected output
```
4
```
Example 2
Input
```
1
1
```
Expected output
```
1
```
Example 3
Input
```
1
1000
```
Expected output
```
1
```
Example 4
Input
```
5
5 4 3 2 1
```
Expected output
```
1
```
Example 5
Input
```
10
1 2 3 4 5 6 7 8 9 10
```
Expected output
```
10
```