Dynamic Programming
9. Longest Increasing Subsequence

Longest Increasing Subsequence (opens in a new tab) Medium

Problem

Given an integer array nums, find the length of the longest strictly increasing subsequence.

Example

Input: nums = [10, 9, 2, 5, 3, 7, 101, 18]

Output: 4

Explanation: The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4.

Summary

To solve this problem, we can use dynamic programming to keep track of the lengths of the longest increasing subsequences ending at each element of the input array. We iterate through the input array and update the lengths accordingly. The length of the longest increasing subsequence is the maximum length found during the iteration.

Solution

In TypeScript

function lengthOfLIS(nums: number[]): number {
    if (nums.length === 0) return 0;
 
    const dp: number[] = Array(nums.length).fill(1);
 
    for (let i = 1; i < nums.length; i++) {
        for (let j = 0; j < i; j++) {
            if (nums[i] > nums[j]) {
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
        }
    }
 
    return Math.max(...dp);
}

In Python

def lengthOfLIS(self, nums: List[int]) -> int:
		if len(nums) == 0:
				return 0
 
		dp = [1] * len(nums)
 
		for i in range(1, len(nums)):
				for j in range(i):
						if nums[i] > nums[j]:
								dp[i] = max(dp[i], dp[j] + 1)
 
		return max(dp)

Step-by-step explanation

  1. If the input array nums is empty, return 0 since the LIS length is 0 in this case.
if (nums.length === 0) return 0;
  1. Create a dp array of the same length as nums and initialize each element to 1. This is because each number in the input array can be considered as an LIS of length 1.
const dp: number[] = Array(nums.length).fill(1);
  1. Iterate through the input array nums using two nested loops. The outer loop runs from index 1 to the end of the array, and the inner loop runs from index 0 to the current index of the outer loop.
for (let i = 1; i < nums.length; i++) {
		for (let j = 0; j < i; j++) {
				// ...
		}
}
  1. For each pair of indices (i, j) where i > j, check if nums[i] is greater than nums[j]. If so, it means there is an increasing subsequence from nums[j] to nums[i].
if (nums[i] > nums[j]) {
		// ...
}
  1. Update the dp[i] value by taking the maximum of its current value and dp[j] + 1. This step ensures that we keep track of the length of the longest increasing subsequence ending at the current index i.
dp[i] = Math.max(dp[i], dp[j] + 1);
  1. After the loops finish, the dp array will store the lengths of the longest increasing subsequences ending at each element in the input array nums. The maximum value in the dp array represents the length of the overall Longest Increasing Subsequence. Use Math.max(...dp) to find and return this value.
return Math.max(...dp);

Complexity Analysis

Time Complexity

The time complexity of this solution is O(n^2), where n is the length of the input array. This is because we use nested loops to iterate through the input array and update the lengths of the longest increasing subsequences.

Space Complexity

The space complexity of this solution is O(n) because we use an array to keep track of the lengths of the longest increasing subsequences.

8. Maximum Product Subarray10. Jump Game