我刚刚编写这个实现来找出 longest increasing subsequence 的长度使用动态规划。因此，对于输入 [10, 22, 9, 33, 21, 50, 41, 60, 80]，LIS 是 6，其中一个集合是 [10, 22, 33, 50, 60, 80]。
当我运行下面的代码时，我得到的正确答案是 6，复杂度为 O(n)。这是对的吗？
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)
最佳答案
使用这个正确、经过验证但效率低下的算法实现来检查您的结果 - 这是标准的递归解决方案，它不使用动态规划:
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)))
检查是否 your_lis(nums) == my_lis(nums) 对于尽可能多的带有数字的不同大小的输入列表，它们应该相等。在某些时候，对于长列表，我的实现会比你的慢得多。
作为进一步的比较点，这是我自己优化的动态规划解决方案。它在 O(n log k) 时间和 O(n) 空间内运行，返回它沿途找到的实际最长递增子序列:
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
关于python - 这个最长公共(public)子序列正确吗？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16120751/