Longest Increasing Subsequence

Your task is to compute the length of the longest increasing subsequence (LIS) in a given array of integers. A subsequence is a sequence derived from the array by deleting some or no elements without changing the order of the remaining elements. The longest increasing subsequence is defined as the one with the maximum length in which all values are strictly increasing.

The input consists of several test cases. For each test case, the first line contains an integer n (representing the number of elements in the array), and the second line contains n space-separated integers. The input terminates with a test case where n = 0 (this test case should not be processed). For each test case, output the length of the longest increasing subsequence on a separate line.

The problem can be formulated using the following LaTeX equation for reference:

\[ \text{LIS}(a_1, a_2, \dots, a_n) = \max_{1 \leq i \leq n}\{\;L_i\;\text{where}\;L_i = 1 + \max_{j < i \;\text{and}\; a_j < a_i} L_j\} \]

An efficient dynamic programming approach with a time complexity of \(O(n^2)\) is acceptable for this problem.

inputFormat

The input is read from standard input (stdin) and consists of multiple test cases. For each test case:

• The first line contains a single integer n ((n > 0)) representing the number of elements in the array.
• The second line contains (n) space-separated integers.

A test case with n = 0 indicates the end of input and should not be processed.

outputFormat

For each test case, output a single integer on a new line representing the length of the longest increasing subsequence of the given array. The output is written to standard output (stdout).## sample

5
10 9 2 5 3
8
10 22 9 33 21 50 41 60
0

2
5

</p>