Longest Increasing Subsequence

You are given an array of integers. Your task is to find the length of the longest increasing subsequence (LIS) in the array. An increasing subsequence is a sequence of numbers where each number is strictly larger than the previous one. Note that the elements in the subsequence do not need to be contiguous in the original array.

Definition: Given an array \( a_1, a_2, \dots, a_n \), a subsequence \( a_{i_1}, a_{i_2}, \dots, a_{i_k} \) is increasing if \( a_{i_1} < a_{i_2} < \cdots < a_{i_k} \). The task is to output the maximum possible \( k \) for which such a subsequence exists.

Example:

Input: 8
       10 9 2 5 3 7 101 18
Output: 4
Explanation: The longest increasing subsequence is [2, 3, 7, 101].

inputFormat

The first line of input contains an integer \( n \) representing the number of elements in the array. The second line contains \( n \) space-separated integers representing the elements of the array.

If \( n = 0 \), the second line will be empty.

outputFormat

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

8
10 9 2 5 3 7 101 18

4