Longest Increasing Subsequence

Given a sequence of integers, your task is to determine the length of the Longest Increasing Subsequence (LIS) in the sequence.

The Longest Increasing Subsequence of a sequence is defined as the longest subsequence where the elements are in strictly increasing order. A subsequence is obtained by deleting some or no elements from the original sequence without changing the order of the remaining elements.

For example, if the input sequence is [10, 9, 2, 5, 3, 7, 101, 18], the longest increasing subsequence is [2, 3, 7, 101] which has a length of 4.

Mathematically, if the sequence is given as \(a_1, a_2, \dots, a_n\), we wish to find the maximum \(k\) such that there exist indices \(1 \leq i_1 < i_2 < \cdots < i_k \leq n\) with \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\).

inputFormat

The first line contains a single integer \(n\) (which can be 0) representing the number of elements in the sequence.

The second line contains \(n\) space-separated integers representing the sequence. If \(n = 0\), the second line will be empty.

outputFormat

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

8
10 9 2 5 3 7 101 18

4