34: Longest increasing subsequence

Given an array of integers, find the length of the longest increasing subsequence (LIS)

 

Example 1

Input: [3, 2, 9, 4, 10, 11, 7]

Output: 4

Explanation: [3, 9, 10, 11] or [2, 9, 10, 11]

Example 2

Input: [3, 2, 1]

Output: 1