Longest Increasing Subsequence

The problem is to find the length of the Longest Increasing Subsequence (LIS) in a given sequence of integers. 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.

Mathematically, if the input sequence is \(a_1, a_2, \dots, a_n\), you need to determine the maximum value of \(k\) such that there exist indices \(i_1 < i_2 < \cdots < i_k\) with \(a_{i_1} < a_{i_2} < \cdots < a_{i_k}\).

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

This problem can be efficiently solved using a dynamic programming approach with binary search.

inputFormat

The input is given via standard input (stdin) and consists of two lines:

• The first line contains a single integer \(n\), which is the number of elements in the sequence.
• The second line contains \(n\) space-separated integers, representing the elements of the sequence.

outputFormat

Output a single integer to standard output (stdout), which is the length of the longest increasing subsequence in the given sequence.

8
10 9 2 5 3 7 101 18

4