Length of the Longest Increasing Subsequence

Given an array of integers, find the length of the longest increasing subsequence.

Input-Output Examples

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

Approach:
Technique: Dynamic Programming

  1. Initialization: Create an array dp where dp[i] represents the length of the LIS ending at index i.
  2. Filling the DP Table:
    • Initialize each element of dp to 1, since the minimum length of LIS ending at each element is 1 (the element itself).
    • Iterate through the array, for each element, iterate through the previous elements to update dp[i] if a longer increasing subsequence is found.
  3. Return: The maximum value in the dp array is the length of the LIS.

C++ Program to find the Length of the Longest Increasing Subsequence

cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

// Function to find the length of the longest increasing subsequence
int lengthOfLIS(vector<int>& nums) {
    if (nums.empty()) return 0;
    int n = nums.size();
    vector<int> dp(n, 1);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    return *max_element(dp.begin(), dp.end());
}

int main() {
    vector<int> nums = {10, 9, 2, 5, 3, 7, 101, 18};
    int length = lengthOfLIS(nums);
    cout << "Length of Longest Increasing Subsequence: " << length << endl;
    return 0;
}

Java Program to find the Length of the Longest Increasing Subsequence

java
import java.util.*;

public class LongestIncreasingSubsequence {
    public static void main(String[] args) {
        int[] nums = {10, 9, 2, 5, 3, 7, 101, 18};
        int length = lengthOfLIS(nums);
        System.out.println("Length of Longest Increasing Subsequence: " + length);
    }

    // Function to find the length of the longest increasing subsequence
    public static int lengthOfLIS(int[] nums) {
        if (nums.length == 0) return 0;
        int n = nums.length;
        int[] dp = new int[n];
        Arrays.fill(dp, 1);
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) {
                    dp[i] = Math.max(dp[i], dp[j] + 1);
                }
            }
        }
        int max = 0;
        for (int length : dp) {
            max = Math.max(max, length);
        }
        return max;
    }
}

Python Program to find the Length of the Longest Increasing Subsequence

python
from typing import List

def lengthOfLIS(nums: List[int]) -> int:
    if not nums:
        return 0
    n = len(nums)
    dp = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
    return max(dp)

if __name__ == "__main__":
    nums = [10, 9, 2, 5, 3, 7, 101, 18]
    length = lengthOfLIS(nums)
    print(f"Length of Longest Increasing Subsequence: {length}")

These codes include the main function and the necessary function for finding the length of the Longest Increasing Subsequence (LIS) using dynamic programming. The lengthOfLIS function calculates the length of the LIS by filling a DP table and returning the maximum value in the table.

DSA

5113

384

Related Articles