Longest Increasing Subsequence of Treasures

You are given a sequence of integers representing the treasure values found on different islands. Your task is to compute the length of the longest increasing subsequence (LIS) in the given sequence.

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 the subsequence where each element is strictly greater than the previous one and its length is maximized.

The solution should implement efficient dynamic programming techniques.

inputFormat

The input consists of two lines. The first line contains an integer n, the number of islands. The second line contains n space-separated integers representing the treasure values on each island. Note that if n is 0, the list is empty.

outputFormat

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

6
1 2 3 4 2 3

4