這是最長的常見子序列是否正確？

我剛剛寫了這個實現來找出使用動態編程的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)

來源

2013-04-20 Srikar Appalaraju

會發生什麼[10，100，20，30，40，50，60，70，80] ？ – johnchen902 2013-04-20 13:25:14

它正確地說LIS的長度是8，這是正確的[10,20,30,40,50,60,70,80] – 2013-04-20 13:28:38

'max（dp_lis）'工作在O（1）複雜性中嗎？ – johnchen902 2013-04-20 13:34:15

我經常實現動態編程算法。

我發現檢查正確性的最佳方法是編寫一個蠻力版本的算法，並將輸出與小例子中的動態編程實現進行比較。

如果兩個版本的輸出一致，那麼你有合理的正確性信心。

來源

2013-04-20 15:54:22 user1149913

使用此正確的，經過驗證的但低效的實現算法來覈對您的結果 - 這是標準的遞歸解決方案，它不使用動態規劃：

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

來源

2013-04-20 15:57:47

這是最長的常見子序列是否正確？

回答

相關問題