A subsequence keeps some elements in their order, not necessarily next to each other. Find the length of the longest strictly increasing subsequence.
Input
The first line has n (1 ≤ n ≤ 500). The second line has the n integers.
Output
The length.
Examples
Example 1 · Input
8 10 9 2 5 3 7 101 18
Expected output
4
Example 2 · Input
6 0 1 0 3 2 3
Expected output
4
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
lis[i] = the length of the longest strictly increasing subsequence that ends at position i.
Hint 2
lis[i] = 1 + max(lis[j]) over j < i with a[j] < a[i] (or 1 if there is none).
Hint 3
The answer is max(lis).
Solution
Show one correct solution (try it yourself first)
n = int(input())
a = list(map(int, input().split()))
lis = [1] * n
for i in range(n):
for j in range(i):
if a[j] < a[i] and lis[j] + 1 > lis[i]:
lis[i] = lis[j] + 1
print(max(lis))