Python – Is this longest public subsequence correct?

I just wrote this implementation to find out the longest increasing subsequence The length of use dynamic programming. Therefore, for input [10, 22, 9, 33, 21, 50, 41, 60, 80], LIS is 6, where the set is [10, 22, 33, 50, 60, 80].

When I run the code below, I get the correct answer is 6 with a complexity of O(n). Is this right?

def lis(a):
    dp_lis     = []
    curr_index = 0
    prev_index = 0

for i in range(len(a)):
        prev_index = curr_index
        curr_index = i

print 'if: %d < %d and %d < %d' % (prev_index, curr_index, a[prev_index], a[curr_index])
        if prev_index < curr_index and a[prev_index] < a[curr_index]:
            print '\tadd ELEMENT: ', a[curr_index]
            new_lis = 1 + max(dp_lis)
            dp_lis.append(new_lis)
        else:
            print '\telse ELEMENT: ', a[curr_index]
            dp_lis.append(1)

print "DP LIST: ", dp_lis
    return max(dp_lis)

if __name__ == '__main__':
    a = [10, 22, 9, 33, 21, 50, 41, 60, 80]
    print lis(a)

Check your results with this correct, proven, but inefficient implementation of the algorithm – this is the standard recursive solution, it does not use dynamic programming:

def lis(nums):
    def max_length(i):
        if i == -1:
            return 0
        maxLen, curLen = 0, 0
        for j in xrange(i-1, -1, -1):
            if nums[j] < nums[i]:
                curLen = max_length(j)
                if curLen > maxLen:
                    maxLen = curLen
        return 1 + maxLen
    if not nums:
        return 0
    return max(max_length(x) for x in xrange(len(nums)))

Check if your_lis(nums)

== my_lis(nums) should be equal for as many input lists of different sizes with numbers as possible. At some point, for long lists, my implementation will be much slower than yours.

As a further point of comparison, this is my own optimized dynamic programming solution. It runs within O(n log k) time and O(n) space, returning the actual longest ascending subsequence it finds along the way:

def an_lis(nums):
    table, lis = lis_table(nums), []
    for i in xrange(len(table)):
        lis.append(nums[table “” not found /]

])
    return lis

def lis_table(nums):
    if not nums:
        return []
    table, preds = [0], [0] * len(nums)
    for i in xrange(1, len(nums)):
        if nums[table “” not found /]

] < nums[i]:
            preds[i] = table[-1]
            table.append(i)
            continue
        minIdx, maxIdx = 0, len(table)-1
        while minIdx < maxIdx:
            mid = (minIdx + maxIdx) / 2
            if nums[table “” not found /]

] < nums[i]:
                minIdx = mid + 1
            else:
                maxIdx = mid
        if nums[i] < nums[table “” not found /]

]:
            if minIdx > 0:
                preds[i] = table[minIdx-1]
            table[minIdx] = i
    current, i = table[-1], len(table)
    while i:
        i -= 1
        table[i], current = current, preds[current]
    return table