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
lakshya1st: 2020-08-28 22:54:05

AC in 1 go :)... Warning : Don't try this at home, school or anywhere!!

s_tank00_: 2020-08-06 18:08:53

very poor test cases no need of memorisation or top down just simple recursion .

kelvin_0179: 2020-05-12 17:28:50

u really dont need to know any iterative algo.... just use a recurrsion tree with an extra element (here 0) at the root and use memoization and the code works!

amansahu112: 2020-04-30 15:58:24

n^2 solution dp

elzahaby: 2019-08-26 19:19:05

DP or Greedy

sajalagrawal14: 2019-06-25 22:38:25

ac using JaliKati Theorem !!!!!

castor21: 2018-06-16 08:20:45

ac in one go using pythagoras' area maximizing theorem on monkeys.O(MERI JAAN) is enough.

Last edit: 2018-06-16 08:22:05
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


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