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.
Mark as read
Unlock Premium Coding Content
On This Page
Your account is free and you can post anonymously if you choose.