Longest Increasing Subsequence

Given an array of integers, determine the length of the longest strictly increasing subsequence in the array.
The subsequence does not have to be contiguous, but the elements must appear in the same order as in the original array.

The problem can be formally described as follows: Given an integer array \(a_1, a_2, \dots, a_n\), find the maximum \(k\) such that there exists indices \(1 \leq i_1 < i_2 < \dots < i_k \leq n\) with \(a_{i_1} < a_{i_2} < \dots < a_{i_k}\).

inputFormat

The first line contains an integer \(n\), representing the number of elements in the array. If \(n > 0\), the second line contains \(n\) space-separated integers. In the case of \(n = 0\), there is no second line.

outputFormat

Output a single integer, which is the length of the longest strictly increasing subsequence of the given array.

9
10 22 9 33 21 50 41 60 80

6