Longest increasing subsequence - MarisaOJ: Marisa Online Judge

You are given an array

$A$ of

$n$ integers, find the longest increasing subsequence (LIS) of

$A$ . In other words, find the largest

$k$ that there exist

$k$ indices

$i_1 < i_2 < ... < i_k$ that

$A_{i_1} < A_{i_2} < ... < A_{i_k}$ . ### Input - The first line contains an integer

$n$ . - The second line contains

$n$ integer

$A_i$ . ### Output - Print the length of the LIS. ### Constraints -

$1 \le n \le 1000$ -

$1 \le A_i \le 10^9$ . ### Example Input:

$5 3 7 2 1 8$

Output:

$3$

#### Note: The LIS is

$(3, 7, 8)$ .

Introduction to dynamic programming
	Hakurei Shrine
	Buying tickets
	Reading 2
	Longest increasing subsequence
	Jealousy
	Maximum path 2
	Fences painting
	Hall
	Knapsack 2
	Longest common subsequence
	Yet another build array problem
	Rectangle cutting
	Palindrome query
	Marisa
	Merging elements
	Brewing potion 8

Topic

Dynamic Programming

Rating

900

Solution (1)

Solution