Hide sidebar
leetcode/DSA courseSystem Design

Longest Increasing Subsequence

Longest Increasing Subsequence

Dynamic Programming
MediumLeetCode #300
30 min

Problem Statement

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

Example

Example 1:
Input:
10
9
2
5
3
7
101
18
LIS:
2
3
7
101

Length: 4

Solution

This problem can be solved using dynamic programming. We'll create a DP array, dp, where dp[i] represents the length of the longest increasing subsequence that ends at index i.

We initialize the dp array with all 1s, since each element itself is an increasing subsequence of length 1. Then, we iterate through the array and for each element nums[i], we iterate through the previous elements nums[j] (where j < i). If nums[i] > nums[j], it means we can potentially extend the subsequence ending at j.

Algorithm Steps (DP)

  • Create a DP array dp of the same size as nums and fill it with 1s.
  • Iterate from i = 1 to n-1.
  • Iterate from j = 0 to i-1.
  • If nums[i] > nums[j], update dp[i] = max(dp[i], 1 + dp[j]).
  • The final answer is the maximum value in the dp array.

Recurrence Relation

dp[i] = max(dp[i], 1 + dp[j])
10
nums[0]
9
nums[1]
2
nums[2]
5
nums[3]
3
nums[4]
7
nums[5]
101
nums[6]
18
nums[7]

DP Table (LIS length ending at index)

Step: 1 / 37
Longest Increasing Subsequence Solution

def lengthOfLIS(nums: list[int]) -> int:
    if not nums:
        return 0

    dp = [1] * len(nums)
    maxLength = 1

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                dp[i] = max(dp[i], dp[j] + 1)
        maxLength = max(maxLength, dp[i])

    return maxLength