Longest Increasing Subsequence

Given an array of integers, find the length of the longest strictly increasing subsequence (LIS) in the array. A subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements.

The problem can be formally defined as follows:

Let \(dp[i]\) be the length of the longest strictly increasing subsequence ending at index \(i\). Then, \[ dp[i] = 1 + \max_{0 \leq j < i \,\text{and}\, a[j] < a[i]} dp[j], \] with the base case \(dp[i] = 1\) if no such \(j\) exists. The answer is \(\max\{dp[i]\}\) for \(0 \leq i < n\).

Note: The subsequence does not need to be contiguous, and the input array may be empty.

inputFormat

The input is read from standard input (stdin) and consists of two lines. The first line contains a single integer \(n\) (\(n \ge 0\)), which denotes the number of elements in the array. The second line contains \(n\) space-separated integers representing the elements of the array.

outputFormat

Output a single integer to standard output (stdout) representing the length of the longest strictly increasing subsequence.

8
10 9 2 5 3 7 101 18

4