## ELIS - Easy Longest Increasing Subsequence

no tags

Given a list of numbers A output the length of the longest increasing subsequence. An increasing subsequence is defined as a set {i0 , i1 , i2 , i3 , ... , ik} such that 0 <= i0 < i1 < i2 < i3 < ... < ik < N and A[ i0 ] < A[ i1 ] < A[ i2 ] < ... < A[ ik ]. A longest increasing subsequence is a subsequence with the maximum k (length).

i.e. in the list {33 , 11 , 22 , 44}

the subsequence {33 , 44} and {11} are increasing subsequences while {11 , 22 , 44} is the longest increasing subsequence.

### Input

First line contain one number N (1 <= N <= 10) the length of the list A.

Second line contains N numbers (1 <= each number <= 20), the numbers in the list A separated by spaces.

### Output

One line containing the lenght of the longest increasing subsequence in A.

### Example

`Input:`
`5`
```1 4 2 4 3
Output:
3```

hide comments
 floofybooper: 2017-12-11 10:54:03 AC in one go using Microsoft Paint hassanarif63: 2016-12-11 08:27:30 #Easy shubh809: 2016-08-14 15:12:40 super easy with LIS rayhan50001: 2016-04-23 19:57:42 Use LIS algorithm..... rayhan50001: 2016-04-23 19:57:06 Easy one.. AC in First Go zubayer_sust: 2016-03-13 20:38:48 got AC !!! Junaid: 2015-12-14 19:10:16 my first DP...AC in one go...;) karthik1997: 2015-10-01 17:57:29 DP rocks :p Alex-ander007: 2015-09-18 01:22:50 AC in one go using dp ^_^ Changming: 2013-07-09 08:27:12 O(N^2) is enough. Because the length of the list A is very small.

 Added by: Omar ElAzazy Date: 2012-03-17 Time limit: 1.948s Source limit: 50000B Memory limit: 1536MB Cluster: Cube (Intel G860) Languages: All except: ASM64