Longest Increasing Subsequence

Given an array of integers, find the length of the Longest Increasing Subsequence (LIS). The subsequence does not necessarily have to be contiguous, but the order of the elements must be maintained.

The LIS is defined as a subsequence that is strictly increasing. For example, for the array [10, 9, 2, 5, 3, 7, 101, 18], one possible longest increasing subsequence is [2, 3, 7, 101] which has a length of 4.

If the array is empty, the output should be 0. Efficient solutions typically use dynamic programming techniques.

inputFormat

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

outputFormat

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

8
10 9 2 5 3 7 101 18

4