这是最长公共子序列正确的？ [英] Is this Longest Common Subsequence Correct?
问题描述
我刚刚写了这个实施找出最长递增子使用动态规划。因此，对于输入为[10，22，9，33，21，50，41，60，80]在LIS是6和该组中的一个是[10，22，33，50，60，80]。
当我运行低于code，我得到了正确的答案，6 O（n）的复杂性。对不对？
高清LIS（一）：
dp_lis = []
curr_index = 0
prev_index = 0
对于在范围I（LEN（一））：
prev_index = curr_index
curr_index = I
打印'，如果：％D＆LT; ％D和％D＆LT; ％D'％（prev_index，curr_index，一个[prev_index]，一个[curr_index]）
如果prev_index＆LT; curr_index和[prev_index] LT; A [curr_index]：
打印'\ TADD元：一个[curr_index]
new_lis = 1 +最大（dp_lis）
dp_lis.append（new_lis）
其他：
打印'\ telse元：一个[curr_index]
dp_lis.append（1）
打印DP LIST，dp_lis
返回MAX（dp_lis）
如果__name__ =='__main__'：
A = [10，22，9，33，21，50，41，60，80]
打印LIS（一）
使用这个正确的，成熟的，但效率低下的执行算法来核对您的结果 - 这是标准的递归解决方案，它不使用动态规划：
高清LIS（NUMS）：
高清MAX_LENGTH（ⅰ）：
如果我== -1：
返回0
MAXLEN，curLen = 0,0
对于j中的xrange第（i-1，-1，-1）：
如果NUMS [J] LT; NUMS [我]：
curLen = MAX_LENGTH（J）
如果curLen＆GT; MAXLEN：
MAXLEN = curLen
返回1 + MAXLEN
如果不是NUMS：
返回0
返回最大值（对于x中的xrange MAX_LENGTH（x）的（LEN（NUMS）））
请检查 your_lis（NUMS）== my_lis（NUMS）与数字尽可能多的不同大小的输入列表，他们应该是平等的。在某些时候，对于长的列表我的实现将远远比你慢。
作为进一步的比较点，这是我自己的优化动态规划解决方案。它运行在 O（N日志K）时间和 O（N）太空，返回实际的最长递增子序列它一路上发现：
高清an_lis（NUMS）：
表，LIS = lis_table（NUMS）[]
对我的xrange（LEN（表））：
lis.append（NUMS [表[I]）
回报LIS
高清lis_table（NUMS）：
如果不是NUMS：
返回 []
表，preDS = [0]，[0] * len个（NUMS）
对我的xrange（1，LEN（NUMS））：
如果NUMS表[-1〕25; NUMS [我]：
preDS [i] =表[-1]
table.append㈠
继续
minIdx，maxIdx = 0，LEN（表）-1-
而minIdx＆LT; maxIdx：
中期=（minIdx + maxIdx）/ 2
如果NUMS表[中旬〕25; NUMS [我]：
minIdx =中等+ 1
其他：
maxIdx =中
如果NUMS [1] - ; NUMS表[minIdx]：
如果minIdx＆GT; 0：
preDS [i] =表[minIdx-1]
表[minIdx] = I
目前，I =表[-1]，len个（表）
当我：
我 - = 1
表[I]，电流=电流，preDS [现行]
返回表
I just wrote this implementation to find out the length of the longest increasing subsequence using dynamic programming. So for input as [10, 22, 9, 33, 21, 50, 41, 60, 80] the LIS is 6 and one of the set is [10, 22, 33, 50, 60, 80].
When I run the below code I get the correct answer as 6 with O(n) complexity. Is it correct?
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)
Use this correct, proven but inefficient implementation of the algorithm to check against your results - it's the standard recursive solution, it doesn't 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 to see if your_lis(nums) == my_lis(nums) for as many different-sized input lists with numbers as possible, they should be equal. At some point, for long lists my implementation will be far slower than yours.
As a further comparison point, here's my own optimized dynamic programming solution. It runs in O(n log k) time and O(n) space, returning the actual longest increasing subsequences it finds along the way:
def an_lis(nums):
table, lis = lis_table(nums), []
for i in xrange(len(table)):
lis.append(nums[table[i]])
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[-1]] < 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[mid]] < nums[i]:
minIdx = mid + 1
else:
maxIdx = mid
if nums[i] < nums[table[minIdx]]:
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
这篇关于这是最长公共子序列正确的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
