Question

How to find the longest increasing subsequence (LIS) of a sequence of numbers in Python

Answer 1

from typing import List

def longest_increasing_subsequence(nums: List[int]) -> int:
    if not nums:
        return 0

    length = [1] * len(nums)
    max_length = 1

    for i in range(1, len(nums)):
        for j in range(i):
            if nums[i] > nums[j]:
                length[i] = max(length[i], length[j] + 1)
        max_length = max(max_length, length[i])

    return max_length

nums = [4, 5, 1, 10, 3, 9, 18, 19]
print(f"Length of LIS: {longest_increasing_subsequence(nums)}")



'''
run:

Length of LIS: 5

'''

 

70+ SQL courses for beginners and professionals