300. Longest Increasing Subsequence

Description

The problem is to find the length of the longest increasing subsequence (LIS) in a given array of integers nums. An increasing subsequence is a subsequence that appears in the same relative order as the original array but not necessarily contiguously and all elements of the subsequence are in strictly increasing order.

Intuition

The intuition behind solving the LIS problem is to use dynamic programming to break down the problem into simpler subproblems. By keeping track of the longest increasing subsequences ending at each index and building up the solution incrementally, we can efficiently determine the overall LIS length. The key is to compare each element with all previous elements and decide whether to include it in the increasing subsequence or not.

Approach

1. Initialization: - Create a 2D array dp of size (n+1) x (n+1), where n is the length of the input array nums. Initialize all elements to 0.
2. Dynamic Programming: - Iterate through the array from the end to the beginning (ind from n-1 to 0). - For each element at index ind, iterate through all previous elements (prev from ind-1 to -1). - For each pair (ind, prev), compute the length of the LIS ending at ind and starting after prev: - Initialize len_ to dp[ind + 1][prev + 1] (the length without including the current element). - If prev is -1 (no previous element) or nums[ind] > nums[prev] (current element can extend the LIS), update len_ to max(len_, 1 + dp[ind + 1][ind + 1]). - Store the computed length in dp[ind][prev + 1].
3. Result: - The length of the longest increasing subsequence is stored in dp[0][0].

Complexity

Time Complexity:

O(n^2), where n is the length of the input array. This is because we have two nested loops iterating through the array.

Space Complexity:

O(n^2), which is the space required for the 2D dp array.

Code

C++

class Solution {
public:
    int lengthOfLIS(std::vector& nums) {
        int n = nums.size();
        std::vector> dp(n + 1, std::vector(n + 1, 0));

        for (int ind = n - 1; ind >= 0; ind--) {
            for (int prev = ind - 1; prev >= -1; prev--) {
                int len = dp[ind + 1][prev + 1];
                if (prev == -1 || nums[ind] > nums[prev]) {
                    len = std::max(len, 1 + dp[ind + 1][ind + 1]);
                }
                dp[ind][prev + 1] = len;
            }
        }
        return dp[0][0];
    }
};

Python

class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        n = len(nums)
        dp = [[0] * (n + 1) for _ in range(n + 1)]

        for ind in range(n - 1, -1, -1):
            for prev in range(ind - 1, -2, -1):
                len_ = dp[ind + 1][prev + 1]
                if prev == -1 or nums[ind] > nums[prev]:
                    len_ = max(len_, 1 + dp[ind + 1][ind + 1])
                dp[ind][prev + 1] = len_
                
        return dp[0][0]

Java

class Solution {
    public int lengthOfLIS(int[] nums) {
        int n = nums.length;
        int[][] dp = new int[n + 1][n + 1];

        for (int ind = n - 1; ind >= 0; ind--) {
            for (int prev = ind - 1; prev >= -1; prev--) {
                int len = dp[ind + 1][prev + 1];
                if (prev == -1 || nums[ind] > nums[prev]) {
                    len = Math.max(len, 1 + dp[ind + 1][ind + 1]);
                }
                dp[ind][prev + 1] = len;
            }
        }
        return dp[0][0];
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        System.out.println(solution.lengthOfLIS(nums)); // Output: 4
    }
}

JavaScript

var lengthOfLIS = function(nums) {
    let dp = Array.from({ length: nums.length+1 }, () => Array(nums.length+1).fill(0));
    for (let ind = nums.length-1; ind >= 0; ind--) {
        for (let prev = ind-1; prev >= -1; prev--) {
            let len = dp[ind+1][prev+1];
            if(prev == -1 || nums[ind] > nums[prev]){
                len = Math.max(len, 1+ dp[ind+1][ind+1]);
            }
            dp[ind][prev+1] = len;
        }
    }
    return dp[0][0];
};