Close Menu
    What's Hot
    Explore the coolest frontend learning platform !
    Visit NamasteDev
    Tuesday, June 23

    Longest Increasing Subsequence

    Updated: Algorithms No Comments1 Min Readdevangini123By

    Problem Statement:

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

    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

    Approach:

    • Use Dynamic Programming (DP) to compute the Longest Increasing Subsequence (LIS).
    • Create a dp array where dp[i] stores the length of the LIS ending at index i.
      • Initialize all dp[i] = 1 (each element alone is an LIS).
    • For each element arr[i], check all previous elements arr[j] (0 ≤ j < i):
      • If arr[j] < arr[i], update dp[i] = max(dp[i], dp[j] + 1).
    • Keep track of the maximum LIS length while filling dp.
    • Return the maximum LIS length.

    Time & Space Complexity:

    Time Complexity: O(n2)

    Space Complexity: O(n)

    Dry Run

    Input: arr = [10, 9, 2, 5, 3, 7, 101, 18]

    Initial:
n = 8
dp = [1, 1, 1, 1, 1, 1, 1, 1]   (each element LIS = 1 initially)
lisLength = 1

i = 1 (arr[1] = 9):
  j = 0 → arr[0]=10 < 9? No
dp = [1, 1, 1, 1, 1, 1, 1, 1], lisLength = 1

i = 2 (arr[2] = 2):
  j = 0 → 10 < 2? No
  j = 1 → 9 < 2? No
dp = [1, 1, 1, 1, 1, 1, 1, 1], lisLength = 1

i = 3 (arr[3] = 5):
  j = 0 → 10 < 5? No
  j = 1 → 9 < 5? No
  j = 2 → 2 < 5? Yes → dp[3] = max(1, dp[2]+1=2) = 2
  lisLength = 2
dp = [1, 1, 1, 2, 1, 1, 1, 1]

i = 4 (arr[4] = 3):
  j = 0 → 10 < 3? No
  j = 1 → 9 < 3? No
  j = 2 → 2 < 3? Yes → dp[4] = max(1, dp[2]+1=2) = 2
  j = 3 → 5 < 3? No
  lisLength = 2
dp = [1, 1, 1, 2, 2, 1, 1, 1]

i = 5 (arr[5] = 7):
  j = 0 → 10 < 7? No
  j = 1 → 9 < 7? No
  j = 2 → 2 < 7? Yes → dp[5] = max(1, 1+1=2) = 2
  j = 3 → 5 < 7? Yes → dp[5] = max(2, 2+1=3) = 3
  j = 4 → 3 < 7? Yes → dp[5] = max(3, 2+1=3) = 3
  lisLength = 3
dp = [1, 1, 1, 2, 2, 3, 1, 1]

i = 6 (arr[6] = 101):
  j = 0 → 10 < 101? Yes → dp[6] = max(1, 1+1=2) = 2
  j = 1 → 9 < 101? Yes → dp[6] = max(2, 1+1=2) = 2
  j = 2 → 2 < 101? Yes → dp[6] = max(2, 1+1=2) = 2
  j = 3 → 5 < 101? Yes → dp[6] = max(2, 2+1=3) = 3
  j = 4 → 3 < 101? Yes → dp[6] = max(3, 2+1=3) = 3
  j = 5 → 7 < 101? Yes → dp[6] = max(3, 3+1=4) = 4
  lisLength = 4
dp = [1, 1, 1, 2, 2, 3, 4, 1]

i = 7 (arr[7] = 18):
  j = 0 → 10 < 18? Yes → dp[7] = max(1, 1+1=2) = 2
  j = 1 → 9 < 18? Yes → dp[7] = max(2, 1+1=2) = 2
  j = 2 → 2 < 18? Yes → dp[7] = max(2, 1+1=2) = 2
  j = 3 → 5 < 18? Yes → dp[7] = max(2, 2+1=3) = 3
  j = 4 → 3 < 18? Yes → dp[7] = max(3, 2+1=3) = 3
  j = 5 → 7 < 18? Yes → dp[7] = max(3, 3+1=4) = 4
  j = 6 → 101 < 18? No
  lisLength = 4
dp = [1, 1, 1, 2, 2, 3, 4, 4]

Final LIS length = 4

    Output: 4 (The LIS is [2, 3, 7, 101] or [2, 3, 7, 18])

    
var lengthOfLIS = function(arr) {
    let n = arr.length;
    let dp = Array(n).fill(1);
    dp[0] = 1;
    let lisLength = 1;
    for (let i = 1; i < n; i++) {
        for (let j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
                lisLength = Math.max(lisLength, dp[i]);
            }
        }
    }
    return lisLength;
};

    
def lengthOfLIS(arr):
    n = len(arr)
    dp = [1] * n
    dp[0] = 1
    lisLength = 1
    for i in range(1, n):
        for j in range(0, i):
            if arr[j] < arr[i]:
                dp[i] = max(dp[i], dp[j] + 1)
                lisLength = max(lisLength, dp[i])
    return lisLength
      
    
public class Solution {
    public static int lengthOfLIS(int[] arr) {
        int n = arr.length;
        int[] dp = new int[n];
        java.util.Arrays.fill(dp, 1);
        dp[0] = 1;
        int lisLength = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                    lisLength = Math.max(lisLength, dp[i]);
                }
            }
        }
        return lisLength;
    }
}

    
#include <vector.h>     
#include <algorithm.h>  

int lengthOfLIS(const std::vector& arr) {
    int n = arr.size();
    std::vector dp(n, 1);
    dp[0] = 1;
    int lisLength = 1;
    for (int i = 1; i < n; ++i) {
        for (int j = 0; j < i; ++j) {
            if (arr[j] < arr[i]) {
                dp[i] = std::max(dp[i], dp[j] + 1);
                lisLength = std::max(lisLength, dp[i]);
            }
        }
    }
    return lisLength;
}

    
#include <stdlib.h>
int lengthOfLIS(int *arr, int n) {
    int *dp = (int*) malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) dp[i] = 1;
    dp[0] = 1;
    int lisLength = 1;
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (arr[j] < arr[i]) {
                int candidate = dp[j] + 1;
                if (candidate > dp[i]) dp[i] = candidate;
                if (dp[i] > lisLength) lisLength = dp[i];
            }
        }
    }
    free(dp);
    return lisLength;
}
 
    
using System;

public class Solution {
    public static int LengthOfLIS(int[] arr) {
        int n = arr.Length;
        int[] dp = new int[n];
        for (int i = 0; i < n; i++) dp[i] = 1;
        dp[0] = 1;
        int lisLength = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) {
                    dp[i] = Math.Max(dp[i], dp[j] + 1);
                    lisLength = Math.Max(lisLength, dp[i]);
                }
            }
        }
        return lisLength;
    }
}
    `

    Keep Reading

    Add A Comment
    Leave A Reply

    Demo

    Courses

    Community

    Contact Us