Longest Increasing Subsequence

Given a sequence of integers, your task is to find the length of the longest increasing subsequence (LIS) within the sequence.

An increasing subsequence is a sequence that is derived from the original sequence by deleting some elements without changing the order of the remaining elements, and each element is strictly greater than the previous one. The problem requires you to compute the maximum length among all possible increasing subsequences.

The solution should read the input from standard input (stdin) and output the result to standard output (stdout).

The formula for updating the dynamic programming state is given by: \[ dp[i] = \max_{0 \leq j a_j} (dp[j] + 1) \] with \(dp[i] = 1\) for each \(i\) if no previous element is smaller.

inputFormat

The first line of input contains an integer \(n\) representing the number of elements in the sequence.

The second line contains \(n\) space-separated integers representing the sequence.

outputFormat

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

8
10 9 2 5 3 7 101 18

4