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:
4
Explanation: The longest increasing subsequence is [2,4,6,12], which has a length of 4.
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.
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
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.)
i = 1
Finally, we return the maximum value in dp as the length of the longest increasing subsequence.
Solution
longest increasing subsequence
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n²) where n is the length of the input array nums. We use two nested for-loops to iterate over all elements in nums.
Space Complexity: O(n) where n is the length of the input array nums. We use an additional array dp of length n to store the length of the longest increasing subsequence ending at each index.