Challenge: Longest Increasing Run (Not Neighbours)

Lab Python Advanced 30 points

Read a list of numbers. Print the length of the longest strictly increasing subsequence – numbers picked from left to right, not necessarily next to each other. For 10 9 2 5 3 7 101 18 the answer is 4 (for example 2 3 7 18).

Input

One line of whole numbers (at most 1000).

Output

One number.

Example

Input

10 9 2 5 3 7 101 18

Output

Sample input available Sample output available

Editor

Python

Hints

best[i] = length of the longest increasing subsequence that ENDS at position i.

best[i] = 1 + max(best[j]) for every j < i with a[j] < a[i].

Solution explanation

O(n²) DP. (With binary search it can be done in O(n log n) – a nice challenge for later!)

Show solution

a = list(map(int, input().split()))
best = [1] * len(a)
for i in range(len(a)):
    for j in range(i):
        if a[j] < a[i] and best[j] + 1 > best[i]:
            best[i] = best[j] + 1
print(max(best))

Output

Answer