Longest Increasing Subsequence

Input

• nums: the integer sequence

Output

the length of longest increasing subsequence

Examples

Example 1:

Input:

nums = [50, 3, 10, 7, 40, 80]

Output: 4

Explanation:

The longest increasing subsequence is [3, 7, 40, 80] which has length 4.

Example 2:

Input:

nums = [1, 2, 4, 3]

Output: 3

Explanation:

Both [1, 2, 4] and [1, 2, 3] are longest increasing subsequences which have length 3.

Try it yourself