Longest Increasing Subsequence

Given an array of integers, your task is to determine the length of the longest strictly increasing subsequence within the array. A subsequence is a sequence derived from the original array by deleting some or no elements without changing the order of the remaining elements.

Mathematically, if the array is \(a_1, a_2,\dots, a_n\), you need to find the maximum \(k\) such that there exist indices \(1 \leq i_1 < i_2 < \dots < i_k \leq n\) with \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\). The classic dynamic programming solution uses the recurrence:

\[ \text{dp}[i] = 1 + \max_{0 \leq j < i \text{ and } a_j < a_i} \text{dp}[j] \]

with the initialization \(\text{dp}[i] = 1\) for all valid \(i\). If the array is empty, the result is 0.

inputFormat

The input begins with an integer n representing the number of elements in the array. The next line contains n space-separated integers.

Note: If n = 0, then there is no second line.

outputFormat

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

8
10 9 2 5 3 7 101 18

4