# Python – Is this longest public subsequence correct?

Is this longest public subsequence correct?… here is a solution to the problem.

## 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]:
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)
``````

### Solution

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)):
])
return lis

def lis_table(nums):
if not nums:
return []
table, preds = ,  * len(nums)
for i in xrange(1, len(nums)):
] < nums[i]:
preds[i] = table[-1]
table.append(i)
continue
minIdx, maxIdx = 0, len(table)-1
while minIdx < maxIdx:
mid = (minIdx + maxIdx) / 2
] < nums[i]:
minIdx = mid + 1
else:
maxIdx = mid
{"ft_lang_label":"__label__en","ft_lang_prob":0.5836272,"math_prob":0.99344915,"size":2503,"snap":"2023-40-2023-50","text_gpt3_token_len":766,"char_repetition_ratio":0.12044818,"word_repetition_ratio":0.045346063,"special_character_ratio":0.33919296,"punctuation_ratio":0.18164437,"nsfw_num_words":0,"has_unicode_error":false,"math_prob_llama3":0.9992669,"pos_list":[0],"im_url_duplicate_count":[null],"WARC_HEADER":"{\"WARC-Type\":\"response\",\"WARC-Date\":\"2023-12-09T15:33:32Z\",\"WARC-Record-ID\":\"<urn:uuid:fb11cc35-73ba-4c2b-bd79-8c2de987a08f>\",\"Content-Length\":\"51166\",\"Content-Type\":\"application/http; msgtype=response\",\"WARC-Warcinfo-ID\":\"<urn:uuid:afef988c-94f0-406c-9b7b-f96ef0e3e782>\",\"WARC-Concurrent-To\":\"<urn:uuid:aa3f902c-b8c4-42f1-9a92-4b78e0f309d5>\",\"WARC-IP-Address\":\"104.21.91.55\",\"WARC-Target-URI\":\"https://etbye.com/python-is-this-longest-public-subsequence-correct/\",\"WARC-Payload-Digest\":\"sha1:KZX2GXKPGC2ASU2GK6MKCWHS475ON45B\",\"WARC-Block-Digest\":\"sha1:RJZY67ZOXZXKVAELBXDPHKCWFACCI7PC\",\"WARC-Identified-Payload-Type\":\"text/html\",\"warc_filename\":\"/cc_download/warc_2023/CC-MAIN-2023-50/CC-MAIN-2023-50_segments_1700679100912.91_warc_CC-MAIN-20231209134916-20231209164916-00558.warc.gz\"}"}