dcsimg
CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4

Thread: Bug in code of Longest Increasing Subsequence problem

  1. #1
    Join Date
    Nov 2015
    Posts
    6

    Bug in code of Longest Increasing Subsequence problem

    Longest Increasing Subsequence
    The Longest Increasing Subsequence problem is to find a subsequence of a given sequence in which the subsequence's elements are in sorted order and in which the subsequence is as long as possible.
    I'm trying to implement a program for Longest Increasing Subsequence, It's giving correct output for some input patterns, But for some it's giving incorrect result. Can anybody tell me where is the bug in the code.
    Here's my code

    Code:
    def binary_search(t, l, r, key):
        while (r - l > 1):
            m = l + (r - l)//2
            if (t[m]>=key):
                r = m
            else:
                l = m
        return r
    
    def LIS():
        tailTable = [0] * N
        tailTable[0] = lst[0]
        len = 1
        for i in range(1, N):
            if (lst[i] < tailTable[0]):
                # New Smallest Value
                tailTable[0] = lst[i]
            elif (lst[i] > tailTable[len - 1]):
                # lst[i] wants to extend largest subsequence
                tailTable[len] = lst[i]
                len += 1
            else:
                # A[i] wants to be current end candidate of an existing
                # subsequence.
                tailTable[binary_search(tailTable, -1, len-1, lst[i])] = lst[i]
        
        return len
        
    if __name__ == "__main__":
        N = int(input())
        
        lst = []
        for i in range(N):
            lst.append(input())
        ret = LIS()
        print(ret)

  2. #2
    Join Date
    Jan 2006
    Location
    Singapore
    Posts
    6,762

    Re: Bug in code of Longest Increasing Subsequence problem

    Quote Originally Posted by atinesh229
    It's giving correct output for some input patterns, But for some it's giving incorrect result.
    Suppose I wanted to help debug your code. I would try the test input patterns, going through the code step by step to see what went right or wrong. But all you said is that "for some it's giving incorrect result". I have no idea what input you tested, so I have to try various input by myself... but why should I do that when you have already done that? It is just a waste of my time (and yours).

    Quote Originally Posted by atinesh229
    Can anybody tell me where is the bug in the code.
    Are you sure that the algorithm is correct?
    C + C++ Compiler: MinGW port of GCC
    Build + Version Control System: SCons + Bazaar

    Look up a C/C++ Reference and learn How To Ask Questions The Smart Way
    Kindly rate my posts if you found them useful

  3. #3
    Join Date
    Nov 2015
    Posts
    6

    Re: Bug in code of Longest Increasing Subsequence problem

    Quote Originally Posted by laserlight View Post
    Suppose I wanted to help debug your code. I would try the test input patterns, going through the code step by step to see what went right or wrong. But all you said is that "for some it's giving incorrect result". I have no idea what input you tested, so I have to try various input by myself... but why should I do that when you have already done that? It is just a waste of my time (and yours).


    Are you sure that the algorithm is correct?
    Test cases that I've tried which worked

    Test Case 1: 0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
    Ans : 6

    Test Case 2: 1, 12, 7, 0, 23, 11, 52, 31, 61, 69, 70, 2
    Ans : 7

    Test Case 3: 6, 3, 5, 2, 7, 8, 1
    Ans : 4

    Test case which is not working is here (Its quite a huge manually cannot be done)
    Test Case 4
    Use this code to run above the test case.


    Actually above test case is from Hacker Rank
    Last edited by atinesh229; July 4th, 2016 at 12:00 PM.

  4. #4
    Join Date
    Nov 2015
    Posts
    6

    Re: Bug in code of Longest Increasing Subsequence problem

    Here is another implementation if you are interested, which still have the same problem

    Code:
    from math import ceil
    
    def LIS():
        #longest_sequence_indices = [None] * (N+1)
        tailTable = [0] * (N+1)
        len = 0
        
        for i in range(N):
            # Binary Search
            low = 1
            high = len
            while low <= high:
                mid = ceil((low + high)/2)
                if (tailTable[mid] < lst[i]):
                    low = mid + 1
                else:
                    high = mid - 1
        
            # low will be length of the longest sequence ending at lst[i]
            longest_len = low
        
            #longest_sequence_indices[longest_len_here] = i
            # The corresponding value
            tailTable[longest_len] = lst[i]
        
            if (longest_len > len):
                len = longest_len
        
        return(len)
    
    if __name__ == "__main__":
        N = int(input())
        
        lst = []
        for i in range(N):
            lst.append(input())
    
        ret = LIS()
        print(ret)

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  


Windows Mobile Development Center


Click Here to Expand Forum to Full Width




On-Demand Webinars (sponsored)