Longest Increasing Subsequence

Given a sequence of integers, your task is to determine the length of the longest strictly increasing subsequence (LIS). A subsequence is a sequence obtained by deleting some or no elements without changing the order of the remaining elements.

The problem can be formally described as follows: Given an array \(a[0 \dots n-1]\), find the maximum \(L\) such that there exists indices \(0 \leq i_1 < i_2 < \dots < i_L < n\) with \[ a[i_1] < a[i_2] < \cdots < a[i_L]. \]

The classic dynamic programming solution uses the recurrence: \[ LIS(i) = \max_{0 \leq j < i \text{ and } a[j] < a[i]} (LIS(j)) + 1 \] with the initialization \(LIS(i) = 1\) for all valid \(i\). In the special case when \(n = 0\), the answer is 0.

inputFormat

The first line of input contains a single integer \(n\) (0 \(\leq n\) \(\leq\) 10⁵) denoting the number of elements in the sequence. The second line contains \(n\) space-separated integers representing the sequence.

outputFormat

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

8
10 9 2 5 3 7 101 18

4