Longest Increasing Subsequence

December 19, 2023

Problem #

Find the longest increasing subsequence in a given sequence of numbers.

Solution #

def longest_increasing_subsequence(nums):
    if not nums:
        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)

# Test the function with an example
print(longest_increasing_subsequence([10, 22, 9, 33, 21, 50, 41, 60, 80]))

In this code, the longest_increasing_subsequence function takes a list of integers as input and returns the length of the longest increasing subsequence in that list. The algorithm works by first initializing a list dp where dp[i] represents the length of the longest increasing subsequence ending at index i. Then, for each element nums[i] in the list, it checks if there is any previous element nums[j] that is smaller than nums[i]. If so, it updates dp[i] to be the maximum of its current value and dp[j] + 1, which represents the length of the longest increasing subsequence ending at index j plus one (for the new element nums[i]). Finally, it returns the maximum value in dp, which represents the length of the longest increasing subsequence in the input list.

When run with the test case [10, 22, 9, 33, 21, 50, 41, 60, 80], this function will return 5, which corresponds to the longest increasing subsequence [10, 22, 33, 50, 60].