Leetcode 300 - Longest Increasing Subsequence

Understanding the problem

The problem statement on LeetCode reads as follows:

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

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Example 1:

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.

Example 2:

Input: nums = [0,1,0,3,2,3]

Output: 4

Explanation: The longest increasing subsequence is [0,1,3,5], therefore the length is 4.

Plan your solution

One way to solve this problem is to use dynamic programming. We can create a table dp where dp[i] represents the length of the longest increasing subsequence ending at index i in the input array. Then, we can iterate through the input array and for each element, we can check the previous elements and update the dp table accordingly. Specifically, for each element nums[i], we can set dp[i] to be the maximum of dp[j] + 1 for all j such that j < i and nums[j] < nums[i]. Finally, we can return the maximum value in the dp table.

Implement your solution

Now that we have a plan, let’s implement it in Python.

class Solution:
    def lengthOfLIS(self, nums):
        # Edge case: if the array is empty, return 0
        if not nums:
            return 0

        # Initialize the dp table with all 1s
        dp = [1] * len(nums)

        # Iterate through the array
        for i in range(1, len(nums)):
            # Iterate through the previous elements
            for j in range(i):
                # If the current element is greater than the previous element, update the dp table
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        # Return the maximum value in the dp table
        return max(dp)

Test your solution

Testing is an important step in the software development process, as it helps ensure that your code is correct and works as intended. In the case of the “Longest Increasing Subsequence” problem, we can test our solution by running a series of test cases that cover different scenarios and edge cases.

For example, we can test our solution with an array that is sorted in increasing order, an array that is sorted in decreasing order, an array that has all the same elements, and an array that has no increasing subsequences. We can also test our solution with arrays of different lengths and with different types of elements (e.g. integers, strings, etc.). By running a variety of test cases, we can gain confidence that our solution is correct and will work for all inputs.

Related:

• longest arithmetic subsequence
• search a 2d matrix ii
• maximum average subarray i