Longest Increasing Subsequence

You are given a sequence of integers. Your task is to determine the length of the longest increasing subsequence (LIS) in the given sequence. An increasing subsequence is defined as a sequence of numbers from the original list where each subsequent number is strictly greater than the previous one. For example, given the array [10, 9, 2, 5, 3, 7, 101, 18] an increasing subsequence is [2, 5, 7, 101] which has a length of 4.

The problem can be formulated using dynamic programming. Let \(dp[i]\) denote the length of the longest increasing subsequence ending at index \(i\). The recurrence is formulated as:

[ dp[i] = 1 + \max_{0 \leq j < i \text{ and } arr[i] > arr[j]} dp[j] \quad (\text{if any such } j \text{ exists}), \quad \text{otherwise } dp[i] = 1. ]

Your program should read the input from standard input and output the result to standard output.

inputFormat

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

Constraints:

• \(0 \le n \le 10^5\) (for practical purposes in competitions, though sample tests use smaller inputs)
• The array elements can be any integer that fits in a standard 32-bit integer.

outputFormat

Output a single integer: the length of the longest increasing subsequence of the given array.

8
10 9 2 5 3 7 101 18

4