Longest Increasing Subsequence

You are given an array of integers. Your task is to compute the length of the longest increasing subsequence (LIS) in the array.

An increasing subsequence is a sequence that can be derived from the array by deleting some or no elements without changing the order of the remaining elements, and where each element is strictly less than the one that follows it. For example, for the array [10, 22, 9, 33, 21, 50, 41, 60, 80], one of the longest increasing subsequences is [10, 22, 33, 50, 60, 80] having length 6.

The problem can be mathematically represented as finding $$\text{LIS} = \max_{0 \le i < n} \{ lis[i] \}$$ where lis[i] denotes the length of the longest increasing subsequence ending at index i.

inputFormat

The first line of input contains a non-negative integer n representing the number of elements in the array. If n = 0, then no further input is given. If n > 0, the second line contains n space-separated integers.

outputFormat

Output a single integer — the length of the longest increasing subsequence in the array.

1
10

1