Longest Increasing Subsequence
Let's solve the Longest Increasing Subsequence problem using Dynamic Programming.
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:
-
nums.length
-
nums[i]
Examples
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.