Longest Increasing Subsequence

Pattern of Problems: Given an array (or list) of items and you'd have to find the largest subset of the items which maintains certain condition


Problem Statement:


Given an integer array nums, return the length of the longest strictly increasing subsequence.
A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:
Input: nums = [10,9,2,5,3,7,101,18]
Output: 4
Explanation: The longest increasing subsequence is [2,3,7,101], therefore the length is 4.

Example 2:
Input: nums = [0,1,0,3,2,3]
Output: 4

Example 3:
Input: nums = [7,7,7,7,7,7,7]
Output: 1

Solution:


Recurrence Relation:


Let arr[0..n-1] be the input array and L(i) be the length of the LIS ending at index i such that arr[i] is the last element of the LIS.
L(i) = 1 + max( L(j) ) where 0 < j < i and arr[j] < arr[i]; or
L(i) = 1, if no such j exists.

To find the LIS for a given array, we need to return max(L(i)) where 0 < i < n.
The length of the longest increasing subsequence ending at index i, will be 1 greater than the maximum of lengths of all longest increasing subsequences ending at indices j such that j is before i, where arr[j] < arr[i].

Java Code:



class Solution {
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] dp = new int[len];
        Arrays.fill(dp, 1);
        int max = 1; 
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }
}

Python Code:


class Solution(object):
    
    # :type nums: List[int]
    # :rtype: int
    def lengthOfLIS(self, nums):
        if nums == None or len(nums) == 0:
            return 0
        
        length = len(nums)
        dp = [1] * length
        maximum = 1
        
        for i in range(length):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)
            maximum = max(maximum, dp[i])
            
        return maximum


Track Path:


Now we will concentrate on printing the longest increasing subsequence. This is how we achieve this: for every element in the array we keep track of the element that comes immediately before it in the longest increasing subsequence. We store this data in parent[] array. Initially all the elements are the parent of its own. The code below will make this process clearer.

Java Code:



Login to Access Content



Python Code:



Login to Access Content




Use Cases:

Most problems where you are given an array (or list) of items and you'd have to find the largest subset of the items which maintains certain condition could be solved using Longest Increasing Subsequence technique.

Template:




Login to Access Content




Take a look at the following problems and you would be able to have a strong grasp on how to effortlessly use the above template to solve a wide variety of problems of the pattern described in the Use Case section:


Instructor:

Abhishek Dey

Abhishek Dey

Senior SDE | Chief Architect

Microsoft | University of Florida

View LinkedIn profile


If you have any feedback, please use this form: https://thealgorists.com/Feedback.


Help Your Friends save 40% on our products

wave