Longest Ordered Subsequence

Interview

Time limit1sMemory limit128 MB

Summary

Given a sequence of N integers, find the length of the longest non-decreasing subsequence.

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

Problem

A numeric sequence $a_i$ is called ordered if $a_1 \le a_2 \le \dots \le a_N$ . For a given sequence $(a_1, a_2, \dots, a_N)$ , a subsequence is any sequence $(a_{i_1}, a_{i_2}, \dots, a_{i_K})$ with $1 \le i_1 < i_2 < \dots < i_K \le N$ .

For example, the sequence $(1, 7, 3, 5, 9, 4, 8)$ has ordered subsequences such as $(1, 7)$ and $(3, 4, 8)$ . All of its longest ordered subsequences have length 4, for example $(1, 3, 5, 8)$ .

Given the sequence, find the length of its longest ordered subsequence.

Input

The first line contains the length of the sequence $N$ ( $1 \le N \le 1000$ ). The second line contains $N$ integers — the elements of the sequence, each in the range from $0$ to $10000$ , separated by spaces.

Output

Print a single integer: the length of the longest ordered subsequence of the given sequence.

Examples3

Example 1
Input
```
7
1 7 3 5 9 4 8
```
Expected output
```
4
```
Example 2
Input
```
1
5
```
Expected output
```
1
```
Example 3
Input
```
5
1 2 3 4 5
```
Expected output
```
5
```