[AMAZON]Length of the LIS
Given an integer array 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
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
Comments
Post a Comment