Longest Increasing Subsequence

Find the length of the longest strictly increasing subsequence using dynamic programming. Each element can be either included or excluded, and we track the best solution at each position.

Dynamic Programming LeetCode 300 ↗ Medium

Problem Statement

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements.

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
Explanation: The longest increasing subsequence is [0,1,2,3].

Interactive Visualization

Array (comma-separated):

Presets:

Speed: 800ms

Current Position

—

LIS Length

Array & DP Values

Ready to start

Code

fun lengthOfLIS(nums: IntArray): Int {    val n = nums.size    val dp = IntArray(n) { 1 }        for (i in 1 until n) {        for (j in 0 until i) {            if (nums[j] < nums[i]) {                dp[i] = maxOf(dp[i], dp[j] + 1)            }        }    }    return dp.max()}

def lengthOfLIS(nums):    n = len(nums)    dp = [1] * n        for i in range(1, n):        for j in range(i):            if nums[j] < nums[i]:                dp[i] = max(dp[i], dp[j] + 1)        return max(dp)

Status & Log

Ready to start

How It Works

Key Insight

The dynamic programming approach builds the solution incrementally. For each position i, we track the length of the longest increasing subsequence ending at that position. We examine all previous elements j < i to see if nums[j] < nums[i], meaning we can extend the subsequence ending at j by including nums[i].

Algorithm Steps

Initialize: Create a DP array where dp[i] = 1 for all positions (each element is a subsequence of length 1)
Outer Loop: For each position i from 1 to n-1
Inner Loop: Check all previous positions j from 0 to i-1
Comparison: If nums[j] < nums[i], we can extend the subsequence:
- dp[i] = max(dp[i], dp[j] + 1)
Result: The maximum value in the DP array is the length of the LIS
Backtrack (optional): Trace back through the DP array to find the actual subsequence

Complexity Analysis

Time Complexity:	O(n²)	Nested loops: outer loop runs n times, inner loop runs i times on average
Space Complexity:	O(n)	DP array stores one value per element

Note: There exists an O(n log n) solution using binary search with a different approach, but the O(n²) DP solution is more intuitive and commonly used in interviews.