Statement

The Longest Increasing Subsequence (LIS) is the longest subsequence from a given array in which the subsequence elements are sorted in strictly increasing order. Given an integer array, nums, find the length of the LIS in this array.

Let’s say we have an integer array [6, 9, 8, 2, 3, 5, 1, 4, 7], and we want to get the longest increasing subsequence in this array. There are multiple increasing subsequences of different lengths, such as [6, 9], [6, 8], [2, 3, 5], [2, 3, 5, 7], and so on. The longest increasing subsequences, in this case, are [2, 3, 4, 7] and [2, 3, 5, 7], both of length 4.

Constraints:

  • 11 \leq nums.length 6000\leq 6000
  • 109-10^9 \leq nums[i] 109\leq 10^9

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.