11. Longest Increasing Subsequence

Given an integer array nums, return the length of the longest strictly increasing.

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

Constraints:

• 1 <= nums.length <= 2500
• -104 <= nums[i] <= 104

Follow up: Can you come up with an algorithm that runs in O(n log(n)) time complexity?

Approach - Binary Search

• First thing is we maintain tail array which means for tail n it will hold the tail of our sequence tail in the sense the last which would be the last element in an increasing sequence
• Second thing is what binary search results if it does not find the element which is {1,,3,4} for searching 2 it would give -2 so our if statement will convert it to 1
• For binary search we give the range
• If index matches size then it means we found a newer element to add if not then we are just replacing the tail with newer least element
• This would O(nlogn) now du to binary search

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        if (n == 0) return 0;
 
        // tails[i] = smallest possible tail value of an increasing subsequence of length (i+1)
        int[] tails = new int[n];
        int size = 0; // tracks how many “slots” in tails are used
        
        for (int x : nums) {
            // binary search for the first index in tails[0..size) where tails[idx] >= x
            int idx = Arrays.binarySearch(tails, 0, size, x);
            if (idx < 0) {
                // binarySearch returns (-insertionPoint - 1) when not found
                idx = -idx - 1;
            }
            tails[idx] = x;
            if (idx == size) {
                // x is bigger than all existing tails, so it extends the LIS
                size++;
            }
        }
        
        return size;
    }
}
 

Approach - DP (Bottom Up)

• If the loop is forward (i from 0 to length), the problem is that we would update the values of d[i] before we’ve had a chance to consider future indices (larger j values) that would help us calculate the correct LIS at each i.
• For example, when i = 0 and you haven’t yet processed i = 1, 2, ..., you can’t yet know what the best subsequence starting at i = 0 could be because you haven’t looked ahead at future elements.
• The reverse loop ensures that by the time you calculate d[i], you have already considered all the potential subsequences starting at later indices, allowing you to build the correct LIS
• Time: O(n^2) Space: O(n)

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

• For better solution we need Binary search
• Similar solution with forward loops, simplest to think is for j dp - j plus the ith element for which we are checking

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

Approach - Memoization

• Just make sure about the p being -1 which cannot be used as an index

class Solution {
    Integer[][] dp;
    public int lengthOfLIS(int[] nums) {
        dp = new Integer[nums.length+1][nums.length+1];
        return dfs(nums, 0, -1);
    }
 
    public int dfs(int[] nums, int i, int p) {
        if (i >= nums.length)
            return 0;
 
        if (p != -1 && dp[i][p] != null) //check
            return dp[i][p];
 
        int take = 0, skip = 0;
        if (p == -1 || nums[i] > nums[p])
            take = 1 + dfs(nums, i+1, i);
        
        skip = dfs(nums, i+1, p);
        if (p != -1) //check
            dp[i][p] = Math.max(take, skip);
        
        return Math.max(take, skip);
    }
}

Approach - Recursion

• we have 2 options take or leave we calculate both and find the max one we use if for take because we can take only on a condition

class Solution {
    public int lengthOfLIS(int[] nums) {
        return dfs(nums, 0, -1);
    }
 
    public int dfs(int[] nums, int i, int p) {
        if (i >= nums.length)
            return 0;
 
        int take = 0, skip = 0;
        if (p == -1 || nums[i] > nums[p])
            take = 1 + dfs(nums, i+1, i);
        
        skip = dfs(nums, i+1, p);
        
        return Math.max(take, skip);
    }
}