• Customer Support: admin@thealgorists.com
  • Feedback: We are listening to your every feedback, and taking action to constantly improve your learning experience. If you have any feedback, please use this form: https://thealgorists.com/Feedback.
  • If you are a student, email to admin@thealgorists.com to get special student discount.



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].

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;
    }
}



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.

class Solution {
    // Track Path
    public int lengthOfLIS(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int len = nums.length;
        int[] dp = new int[len];
        int[] parent = new int[len]; // to track path

        // initialize
        Arrays.fill(dp, 1);
        for (int i = 0; i < len; i++) {
            parent[i] = i;
        }
        
        int max = 1; 
        int end = 0; // end index of the longest increasing subsequence
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    parent[i] = j;
                }
            }
            if (max < dp[i]) {
                max = dp[i];
                end = i;
            }
        }
        
        // print path
        Deque<Integer> stack = new ArrayDeque();
        while (parent[end] != end) {
            stack.push(nums[end]);
            end = parent[end];
        } 
        stack.push(nums[end]);
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }
        
        
        return max;
    }
}



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:



public int solve(int[] nums) {
        int len = nums.length;
        int[] lis = new int[len];
        Arrays.fill(lis, APPROPRIATE_VALUE); // APPROPRIATE_VALUE will vary from problem to problem depending on the problem statement
        int max = 1; 
        for (int i = 1; i < len; i++) {
            for (int j = 0; j < i; j++) {
                if (condition(nums[i], nums[j])) { // implementation of condition() method will vary according to the given problem statement 
                    dplisi] = Math.max(lis[i], lis[j] + value_for_nums_i)); // value_for_nums_i will be determined according to the problem statement
                }
            }
            max = Math.max(max, lis[i]);
        }
        return max;
    }



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:


The above content is written by:

Abhishek Dey

Abhishek Dey

A Visionary Software Engineer With A Mission To Empower Every Person & Every Organization On The Planet To Achieve More

Microsoft | University of Florida

View LinkedIn profile


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




Subscribe to Our Youtube Channel

Follow Us On LinkedIn
wave