### [AMAZON]Length of the LIS

Given an integer array

A longest increasing subsequence is defined as a subsequence in the given sequence of integers such that the elements in the subsequence are in sorted order, lowest to highest and in which the subsequence is as long as possible

1, 2, 3

3

The sequence in itself is an increasing one

4, 5, 6, 7, 8, 1, 2, 1, 2, 3, 5, 4, 6, 7, 8, 9, 0, 6, 7

8

The length of the LIS is 8. The LIS elements from the sequence are highlighted: 4, 5, 6, 7, 8, 1, 2,

**sequence**, return the**length**of the longest increasing subsequence (LIS)A longest increasing subsequence is defined as a subsequence in the given sequence of integers such that the elements in the subsequence are in sorted order, lowest to highest and in which the subsequence is as long as possible

**Sample Test Cases:****Input #00:**1, 2, 3

**Output:**3

**Explanation:**The sequence in itself is an increasing one

**Input #01:**4, 5, 6, 7, 8, 1, 2, 1, 2, 3, 5, 4, 6, 7, 8, 9, 0, 6, 7

**Output #01:**8

**Explanation:**The length of the LIS is 8. The LIS elements from the sequence are highlighted: 4, 5, 6, 7, 8, 1, 2,

**1, 2, 3, 5**, 4,**6,7, 8, 9**, 0, 6, 7