Need Help Understanding Longest Increasing Subsequence Problem

Part 1 (2019)
1

Hello everyone,

I’ve been trying to solve the “Longest Increasing Subsequence” problem using Python, and I’ve been following the tutorial on the Longest Increasing Subsequence Python. While the article provides a good explanation, I’m still having some trouble with the actual implementation.

Here’s the problem description briefly: Given an array of numbers, find the length of the longest increasing subsequence.

I’ve tried to implement the solution based on the article, but I’m running into some issues. Here’s my code so far:

pythonCopy code

# Python code for Longest Increasing Subsequence
def longest_increasing_subsequence(nums):
    n = len(nums)
    lis = [1] * n

    for i in range(1, n):
        for j in range(0, i):
            if nums[i] > nums[j] and lis[i] < lis[j] + 1:
                lis[i] = lis[j] + 1

    return max(lis)

# Example usage
nums = [10, 22, 9, 33, 21, 50, 41, 60, 80]
result = longest_increasing_subsequence(nums)
print("Length of Longest Increasing Subsequence:", result)

I’d appreciate it if someone could review my code and help me understand where I might be going wrong.

Thank you

2

Hello,

Could you please specify the problem you are encountering? The code you have provided appears correct to me and is identical to the dynamic programming solution in the InterviewBit tutorial.