Windows 7 Issues with understanding the Longest Increasing Subsequence code

Rishab7

New Member
Joined
Apr 17, 2023
Messages
21
Hello all,

I am having issues understanding the code posted on this blog for the Longest Increasing Subsequence problem. I've been trying to implement the code, but I haven't been able to get the correct output. The code I've been trying to implement is as follows:
Code: 
def LIS(A):
    n = len(A)
    lis = [1]*n
    for i in range (1 , n):
        for j in range(0 , i):
            if A[i] > A[j] and lis[i]< lis[j] + 1 :
                lis[i] = lis[j]+1
    maximum = 0
    for i in range(n):
        maximum = max(maximum , lis[i])
    return maximum

I've tried to debug it, but I'm still having issues. Can someone please help me understand what I'm doing wrong?

Thank you!
 
Last edited by a moderator:
Solution
The code you've provided is a Python implementation of the Longest Increasing Subsequence (LIS) problem. The LIS problem is a classic dynamic programming problem that aims to find the length of the longest subsequence of a given sequence of numbers that is strictly increasing. The code you posted correctly implements the dynamic programming approach to solve the LIS problem. Here is a brief explanation of how the code works: 1. Initialization: The code initializes an array lis of the same length as the input array A, where lis[i] represents the length of the LIS ending at index i. 2. Dynamic Programming Iteration: It then iterates through each element of the input array A. For each element...
Sort by date Sort by votes
The code you've provided is a Python implementation of the Longest Increasing Subsequence (LIS) problem. The LIS problem is a classic dynamic programming problem that aims to find the length of the longest subsequence of a given sequence of numbers that is strictly increasing. The code you posted correctly implements the dynamic programming approach to solve the LIS problem. Here is a brief explanation of how the code works: 1. Initialization: The code initializes an array lis of the same length as the input array A, where lis[i] represents the length of the LIS ending at index i. 2. Dynamic Programming Iteration: It then iterates through each element of the input array A. For each element at index i, it loops through all elements before i (from 0 to i) to check if the current element can be added to form a longer increasing subsequence. 3. Updating lis Array: If the current element A[i] is greater than the element at index j, and adding the current element A[i] to the LIS ending at j would increase the length, then the LIS ending at i is updated to be one more than the LIS ending at j. 4. Finding Maximum Length: Finally, the code finds the maximum value in the lis array, which represents the length of the overall longest increasing subsequence. If you are still facing issues with the code, it might be helpful to run the code on some test cases and print intermediate results to understand how the dynamic programming algorithm works step by step. Additionally, you can share any specific input examples where you are encountering unexpected output for further assistance.
 
Upvote 0 Downvote
Solution
You must log in or register to reply here.