最长的子序列问题的代码中的错误

本文介绍了最长的子序列问题的代码中的错误的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 最长增加子序列 最长增加子序列问题是找到给定序列的子序列，其中子序列的元素按排序顺序且子序列为尽可能长的 我正在尝试实现最长增加子序列的程序，它为某些输入模式提供了正确的输出，但是对于一些人给出错误的结果。任何人都可以告诉我代码中的错误在哪里。 我尝试了什么： 这是我的代码 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 i 范围内（ 1 ，N）： if （lst [i]< tailTable [ 0 ]）： ＃ 新最小值 tailTable [ 0 ] = lst [i] elif （lst [i]> tailTable [len - 1 ]）： ＃ lst [i]想扩展最大的子序列 tailTable [len] = lst [i] len + = 1 其他： ＃ A [i]希望成为现有的最终候选者 ＃ 子序列。 tailTable [binary_search（tailTable， - 1 ，len- 1 ，lst [i]）] = lst [i] return len if __name__ == __ main __： N = int（input（）） lst = [] i 范围内（N） ： lst.append（input（）） ret = LIS（） print （ret） 解决方案 我不熟悉Python，但你应该试试这个： def LIS（）： lenmax = 1 len = 1 i 范围内（ 1 ，N）： if （lst [i- 1 ]< lst [i]）： ＃ 按顺序 len + = 1 if （len> lenmax）： lenmax = len else ： ＃ 新序列 len = 1 return lenmax Longest Increasing SubsequenceThe 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 possibleI'm trying to implement a program for Longest Increasing Subsequence, Its giving correct output for some input patterns, But for some its giving incorrect result. Can anybody tell me where is the bug in the code.What I have tried:Here is my codedef 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 rdef 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) 解决方案 I am not fluent in Python, but you should try this:def LIS(): lenmax = 1 len = 1 for i in range(1, N): if (lst[i-1] < lst[i]): # in sequence len += 1 if (len > lenmax): lenmax = len else: # new sequence len = 1 return lenmax 这篇关于最长的子序列问题的代码中的错误的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！