Longest Increasing Subsequence
DESCRIPTION (credit 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).
EXAMPLES
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.
Run your code to see results here
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 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)
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.)
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)
Finally, we return the maximum value in dp as the length of the longest increasing subsequence.
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)
Complexity Analysis
Time Complexity: O(n2) 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.
Loading comments...