Longest Increasing Subsequence

You are given an array of integers. Your task is to determine the length of the longest strictly increasing subsequence (LIS) in the array. A subsequence is derived from the array by removing some or no elements without changing the order of the remaining elements.

Formally, given an integer array \(A = [a_1, a_2, \dots, a_n]\), find the maximum length \(L\) of a subsequence \(\{a_{i_1}, a_{i_2}, \dots, a_{i_L}\}\) such that \(a_{i_1} < a_{i_2} < \dots < a_{i_L}\). This classical dynamic programming problem can be solved in \(O(n^2)\) time using the method described below.

inputFormat

The input is given via standard input (stdin). The first line contains an integer \(n\) representing the number of elements in the array. The second line contains \(n\) space-separated integers that represent the array.

outputFormat

Output the length of the longest strictly increasing subsequence to standard output (stdout).

8
10 9 2 5 3 7 101 18

4