最长增加的子序列2d

Question

我有 n排序阵列 m整数按固定顺序排列。我需要找到一个最长的递增子序列，这样子序列中的每个元素都只属于一个数组。我能做得比 O（n ）？

Answer 1

符合@svs，这是不可能达到小于O（m * n）。但是，在实践中，一旦知道不可能在其中找到更长的子序列，就可以通过终止数组中的迭代来减少平均最差时间。

琐碎的循环：

maxList = [] 
for arr in arrays: 
    last = arr[0] - 1 
    tempList = [] 
    for element in arr: 
     if element > last: 
      tempList.append(element) 
      if len(tempList) > len(maxList): 
        maxList = tempList 

     else: 
      tempList = [element] 
     last = element 

return (maxList, iters) 

凭借冗余循环迭代忽略：

maxList = [] 
for arr in arrays: 
    if len(maxList) == len(arr): 
     break 

    last = arr[0] - 1 
    tempList = [] 
    for (index, element) in enumerate(arr): 
     if element > last: 
      tempList.append(element) 
      if len(tempList) > len(maxList): 
        maxList = tempList[:] 
     else: 
      tempList = [element] 

     # if continuing looking down the array could not result in a longer 
     # increasing sequence 
     if (len(tempList) + (len(arr) - (index + 1)) <= len(maxList)): 
      break 

     last = element 

return (maxList, iters)