Longest Increasing Subsequence

Given a sequence of integers, find the length of the longest strictly increasing subsequence. A subsequence is a sequence that can be derived from the original sequence by deleting some elements without changing the order of the remaining elements.

You are given an array of \(n\) integers. Define \(dp[i]\) as the length of the longest strictly increasing subsequence ending at index \(i\). The recurrence relation is given by:

\[ dp[i] = \max_{0 \le j < i \ \text{and} \ nums[j] < nums[i]}\{dp[j]\} + 1 \]

Your task is to compute and output the maximum value among all \(dp[i]\), which represents the length of the longest increasing subsequence in the array.

inputFormat

The input is read from standard input (stdin). The first line contains an integer \(n\), representing the number of elements in the sequence. The second line contains \(n\) space-separated integers.

outputFormat

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

7
10 9 2 5 3 7 101

4