Dynamic Programming
Longest Increasing Subsequence
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
def longest_increasing_subsequence(nums):if not nums:return 0n = len(nums)dp = [1] * nfor 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
def longest_increasing_subsequence(nums):if not nums:return 0n = len(nums)dp = [1] * nfor 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
Solution
def longest_increasing_subsequence(nums):if not nums:return 0n = len(nums)dp = [1] * nfor 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
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.
Your account is free and you can post anonymously if you choose.