Longest Increasing Subsequence

Given an array of integers, find the length of the longest strictly increasing subsequence (LIS).

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. Formally, for a sequence \(a_1, a_2, \dots, a_n\), you need to find the maximum integer \(L\) such that there exists indices \(1 \leq i_1 < i_2 < \cdots < i_L \leq n\) with \(a_{i_1} < a_{i_2} < \cdots < a_{i_L}\).

The expected time complexity is \(O(n^2)\).

inputFormat

The first line of input contains a single integer \(n\) (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 --- the length of the longest increasing subsequence in the given array.

8
10 9 2 5 3 7 101 18

4