Longest Increasing Subsequence

You are given a sequence of doll heights. Your task is to determine the length of the longest strictly increasing subsequence. Formally, given an array \(a_1, a_2, \dots, a_n\), find the maximum length \(L\) such that there exists indices \(1 \le i_1 < i_2 < \cdots < i_L \le n\) with \(a_{i_1} < a_{i_2} < \cdots < a_{i_L}\).

The recurrence relation for dynamic programming is given by:

\[ \text{dp}[i] = 1 + \max_{0 \le j < i \text{ and } a[j] < a[i]} \text{dp}[j] \]

If no such \(j\) exists, then \(\text{dp}[i] = 1\). Your goal is to compute \(\max_{0 \le i < n} \text{dp}[i]\).

inputFormat

The first line of input contains a single integer \(n\) (the number of dolls). The second line contains \(n\) space-separated integers representing the heights of the dolls.

outputFormat

Output a single integer: the length of the longest strictly increasing subsequence.

6
5 1 8 3 6 10

4