Dynamic Programming

Longest Increasing Subsequence

medium

DESCRIPTION (inspired by Leetcode.com)

Given an integer array nums, write a function that returns the length of the longest increasing subsequence within the array. The subsequence does not have to be contiguous, but the elements must be strictly increasing (i.e. nums[i] < nums[j] for all i < j).

Input:

nums = [8,2,4,3,6,12]

Output:

Explanation: The longest increasing subsequence is [2,4,6,12], which has a length of 4.

Code Editor

Run your code to see results here

Have suggestions or found something wrong?

Explanation

This solution uses bottom-up dynamic programming to solve the problem. We create an integer array dp of length n where n is the length of the input array nums. dp[i] is equal to length of the longest increasing subsequence ending at the i-th index of nums. Since a single element is an increasing subsequence of length 1, we initialize dp with 1 for all elements.

Visualization


def longest_increasing_subsequence(nums):
  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)

longest increasing subsequence

0 / 1

We then use a for-loop i to iterate over each index in the array. The body of the loop determines the correct value for dp[i].

Inside the body of the loop, we use another for-loop j to iterate over all indexes before i. If nums[i] > nums[j], we update dp[i] to be the maximum of dp[i] and dp[j] + 1. This is because the i-th element can extend the increasing subsequence ending at the j-th element by 1. (If dp[i] is already greater than dp[j] + 1, we leave it as is - a longer subsequence ending at i has already been found.)

Visualization


def longest_increasing_subsequence(nums):
  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)

i = 1

0 / 5

Finally, we return the maximum value in dp as the length of the longest increasing subsequence.

Solution

Try these examples:

Visualization


def longest_increasing_subsequence(nums):
  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)

longest increasing subsequence

0 / 32

What is the time complexity of this solution?

O(V + E)

O(N + Q)

O(n²)

O(4^L)

Mark as read

Next: Word Break