找到列表中的最长子序列

huangapple
go评论97阅读模式
英文:

Find longest subsequence in a list

问题

我想编写一个在线性时间内找到列表中最长升序序列的函数。这似乎是一个非常简单的任务，但是没有嵌套的for循环，我有些卡住。我的想法如下：

  1. if len(L) == 0 or len(L) == 1:
  2.     return len(L)
  4. if all(L[i] == L[0] for i in range(len(L)-1)):
  5.     return len(L)
  7. left = [1] * len(L)
  8. right = [1] * len(L)
  9. count = 1
  10. for i in range(len(L)-1):
  11.     if L[i] <= L[i+1]:
  12.         count += 1
  13.         left[i+1] = count
  14.     else:
  15.         count = 1
  16.         left[i+1] = count
  18. count = 1
  19. for i in range(len(L)-1, -1, -1):
  20.     if L[i] <= L[i-1]:
  21.         count += 1
  22.         right[i-1] = count
  23.     else:
  24.         count = 1
  25.         right[i-1] = count
  27. idx_left = left.index(max(left))
  28. idx_right = right.index(max(right))
  30. if max(max(left), max(right)) == max(left) and idx_left == len(left) - 1:
  31.     return max(left)

请注意，这是您提供的代码的翻译部分。如果您有任何其他问题或需要进一步的解释，请随时告诉我。

英文:

I want to write a function that finds the longest ascending sequence in a list in linear time. This seems like a really easy task but without nested for-loops I am stuck somehow. My idea was the following:

  1. if len(L) == 0 or len(L) == 1:
  2.     return len(L)
  4. if all(L[i] == L[0] for i in range(len(L)-1)):
  5.     return len(L)
  7. left = [1] * len(L)
  8. right = [1] * len(L)
  9. count = 1
  10. for i in range(len(L)-1):
  11.     if L[i] &lt;= L[i+1]:
  12.         count += 1
  13.         left[i+1] = count
  14.     else:
  15.         count = 1
  16.         left[i+1] = count
  18. count = 1
  19. for i in range(len(L)-1, -1, -1):
  20.     if L[i] &lt;= L[i-1]:
  21.         count += 1
  22.         right[i-1] = count
  23.     else:
  24.         count = 1
  25.         right[i-1] = count
  27. idx_left = left.index(max(left))
  28. idx_right = right.index(max(right))
  30. if max(max(left), max(right)) == max(left) and idx_left == len(left) - 1:
  31.     return max(left)

答案1

得分: 1

你可以尝试这样做：

  1. mylist=[10,9,8,10,6,5,4,3,2,3]
  2.     
  3. previous  = mylist[0]
  4. max_sublist = [previous]
  5. current_sublist = [previous]
  6. increasing = True
  7.     
  8. for x in mylist[1:]:
  9.     if increasing and previous <= x:
  10.         current_sublist.append(x)
  11.     elif previous >= x:
  12.         increasing = False
  13.         current_sublist.append(x)
  14.     else:
  15.         if len(current_sublist) > len(max_sublist):
  16.             max_sublist = current_sublist[:]
  17.         current_sublist = [previous, x]
  18.         increasing = True
  19.     previous = x
  20.     
  21. if len(current_sublist) > len(max_sublist):
  22.     max_sublist = current_sublist[:]
  23.     
  24. print(f"{max_sublist=}\n{len(max_sublist)=}")
英文:

You can try this:

  1. mylist=[10,9,8,10,6,5,4,3,2,3]
  3. previous  = mylist[0]
  4. max_sublist = [previous]
  5. current_sublist = [previous]
  6. increasing = True
  8. for x in mylist[1:]:
  9.     if increasing and previous &lt;= x:
  10.         current_sublist.append(x)
  11.     elif previous &gt;= x:
  12.         increasing = False
  13.         current_sublist.append(x)
  14.     else:
  15.         if len(current_sublist) &gt; len(max_sublist):
  16.             max_sublist = current_sublist[:]
  17.         current_sublist = [previous, x]
  18.         increasing = True
  19.     previous = x
  21. if len(current_sublist) &gt; len(max_sublist):
  22.             max_sublist = current_sublist[:]
  24. print(f&quot;{max_sublist=}\n{len(max_sublist)=}&quot;)

It gives:

  1. max_sublist=[8, 10, 6, 5, 4, 3, 2]
  2. len(max_sublist)=7

答案2

得分: 1

尝试处理两个值之间的差异，我不确定它适用于每种情况，但这是一个O(n)的开始，

最终在结果中加1，因为它在计算比较次数时，最后一个值不会被计算。

  1. def sequence(seq):
  2.     max_len = 0
  3.     current_len = 0
  4.     going_down = False
  5.     for i in range(len(seq)-1):
  6.         if seq[i] == seq[i+1]:
  7.             current_len += 1
  8.             if max_len < current_len:
  9.                 max_len = current_len
  10.             continue
  11.         if seq[i] < seq[i+1]:
  12.             if going_down:
  13.                 current_len = 1
  14.                 going_down = False
  15.                 continue
  16.             else:
  17.                 current_len += 1
  18.                 if max_len < current_len:
  19.                     max_len = current_len
  20.                 continue
  22.         if seq[i] > seq[i+1]:
  23.             if going_down:
  24.                 current_len += 1
  25.                 if max_len < current_len:
  26.                     max_len = current_len
  27.                 continue
  28.             else:
  29.                 going_down = True
  30.                 current_len += 1
  31.                 if max_len < current_len:
  32.                     max_len = current_len
  33.     return max_len + 1

[10, 9, 8, 10, 6, 5, 4, 3, 2, 3] # 7
[4, 5, 3, 2, 1, 3, 6, 4, 7] # 5
[10, 9, 8, 7, 6, 5, 4, 3, 2, 3] # 9
[10, 9, 8, 7, 6, 5, 4, 3, 2, 1] # 10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10] # 10
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] # 19
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # 10
[0, 0, 0, 0, 0, 0, 0, 0, 0, 1] # 10
[1, 0, 0, 0, 0, 0, 0, 0, 0, 1] # 9
[1, 1, 0, 0, 0, 0, 0, 0, 0, 1] # 9
[1, 1, 1, 0, 0, 0, 0, 0, 0, 2] # 9

英文:

try working on the diffrences between 2 values,
I'm not sure it works for every case but it's a start in o(n),

added 1 to the resault in the end cause it's counting comparisons so the last value will not be counted

  1. def sequance(seq):
  2. max_len = 0
  3. current_len = 0
  4. going_down = False
  5. for i in range(len(seq)-1):
  6.     if seq[i] == seq[i+1]:
  7.         current_len += 1
  8.         if max_len &lt; current_len:
  9.             max_len = current_len
  10.         continue
  11.     if seq[i] &lt; seq[i+1]:
  12.         if going_down:
  13.             current_len = 1
  14.             going_down = False
  15.             continue
  16.         else:
  17.             current_len +=1
  18.             if max_len &lt; current_len:
  19.                 max_len = current_len
  20.             continue
  22.     if seq[i] &gt; seq[i+1]:
  23.         if going_down:
  24.             current_len += 1
  25.             if max_len &lt; current_len:
  26.                 max_len = current_len
  27.             continue
  28.         else:
  29.             going_down = True
  30.             current_len += 1
  31.             if max_len &lt; current_len:
  32.                 max_len = current_len
  33. return max_len + 1
  35. [10, 9, 8, 10, 6, 5, 4, 3, 2, 3] #    7
  36. [4, 5, 3, 2, 1, 3, 6, 4, 7] #    5
  37. [10, 9, 8, 7, 6, 5, 4, 3, 2, 3] #    9
  38. [10, 9, 8, 7, 6, 5, 4, 3, 2, 1] #    10
  39. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] #    10
  40. [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1] #    19
  41. [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] #    10
  42. [0, 0, 0, 0, 0, 0, 0, 0, 0, 1] #    10
  43. [1, 0, 0, 0, 0, 0, 0, 0, 0, 1] #    9
  44. [1, 1, 0, 0, 0, 0, 0, 0, 0, 1] #    9
  45. [1, 1, 1, 0, 0, 0, 0, 0, 0, 2] #    9

答案3

得分: 1

你可以考虑分组相同值的增加/减少状态，并跟踪前一个长度。该算法的复杂度是O(n)，只需一次输入遍历：

  1. from itertools import groupby
  3. def sequence(lst):
  4.     max_len = 0
  5.     prev = float('nan')
  6.     prev_len = 0
  7.     running_len = 0
  8.     increasing = False
  9.     for k, g in groupby(lst):
  10.         L = len(list(g))
  11.         if k < prev:
  12.             running_len += L
  13.             increasing = False
  14.         else:
  15.             if increasing:
  16.                 running_len += L
  17.             else:
  18.                 max_len = max(max_len, running_len)
  19.                 running_len = L + prev_len
  20.                 increasing = True
  21.         prev = k
  22.         prev_len = L
  24.     return max(max_len, running_len)
  26. sequence([10, 9, 8, 10, 6, 5, 4, 3, 2, 3])

输出: 7

注意: itertools.groupby 只是一种方便的方法，用于避免处理连续相同的值。但你不必使用它，可以自己跟踪这些值。

其他示例：

  1. sequence([10, 9, 8, 10, 6, 5, 4, 3, 2, 3])
  2. # 7               *   *  *  *  *  *  *
  4. sequence([4, 5, 3, 2, 1, 3, 6, 4, 7])
  5. # 5        *  *  *  *  *
  7. sequence([10, 9, 8, 7, 6, 5, 4, 3, 2, 3])
  8. # 9         *  *  *  *  *  *  *  *  *
  10. sequence([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
  11. # 10        *  *  *  *  *  *  *  *  *  *
  13. sequence([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  14. # 10       *  *  *  *  *  *  *  *  *   *
  16. sequence([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
  17. # 19       *  *  *  *  *  *  *  *  *   *  *  *  *  *  *  *  *  *  *
  19. sequence([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
  20. # 10       *  *  *  *  *  *  *  *  *  *
  22. sequence([0, 0, 0, 0, 0, 0, 0, 0, 0, 1])
  23. # 10       *  *  *  *  *  *  *  *  *  *
  25. sequence([1, 0, 0, 0, 0, 0, 0, 0, 0, 1])
  26. # 9           *  *  *  *  *  *  *  *  *
  28. sequence([1, 1, 0, 0, 0, 0, 0, 0, 0, 1])
  29. # 9        *  *  *  *  *  *  *  *  *
  31. sequence([1, 1, 1, 0, 0, 0, 0, 0, 0, 2])
  32. # 9        *  *  *  *  *  *  *  *  *

重构代码

这是与上面相同的逻辑，但进行了代码重构，测试已合并，中间变量已删除等。

  1. from itertools import groupby
  3. def sequence(lst):
  4.     max_len = prev_len = running_len = 0
  5.     prev = float('nan')
  6.     decreasing = False
  7.     for k, g in groupby(lst):
  8.         if k < prev:
  9.             decreasing = True
  10.         elif decreasing:
  11.             max_len = max(max_len, running_len)
  12.             running_len = prev_len
  13.             decreasing = False
  14.         prev = k
  15.         prev_len = len(list(g))
  16.         running_len += prev_len
  18.     return max(max_len, running_len)
英文:

You can consider the increasing/decreasing state of grouped identical values, and keep track of the previous length. The complexity is O(n) with a single pass on the input:

  1. from itertools import groupby
  3. def sequence(lst):
  4.     max_len = 0
  5.     prev = float(&#39;nan&#39;)
  6.     prev_len = 0
  7.     running_len = 0
  8.     increasing = False
  9.     for k, g in groupby(lst):
  10.         L = len(list(g))
  11.         if k &lt; prev:
  12.             running_len += L
  13.             increasing = False
  14.         else:
  15.             if increasing:
  16.                 running_len += L
  17.             else:
  18.                 max_len = max(max_len, running_len)
  19.                 running_len = L + prev_len
  20.                 increasing = True
  21.         prev = k
  22.         prev_len = L
  24.     return max(max_len, running_len)
  26. sequence([10,9,8,10,6,5,4,3,2,3])

Output: 7

NB. itertools.groupby is just a convenience to avoid having to handle the successive identical values. But you don't have to use it and can track those yourself.

Other examples:

  1. sequence([10, 9, 8, 10, 6, 5, 4, 3, 2, 3])
  2. #7               *   *  *  *  *  *  *
  4. sequence([4, 5, 3, 2, 1, 3, 6, 4, 7])
  5. #5        *  *  *  *  *
  7. sequence([10, 9, 8, 7, 6, 5, 4, 3, 2, 3])
  8. #9         *  *  *  *  *  *  *  *  *
  10. sequence([10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
  11. #10        *  *  *  *  *  *  *  *  *  *
  13. sequence([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])
  14. #10       *  *  *  *  *  *  *  *  *   *
  16. sequence([1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1])
  17. #19       *  *  *  *  *  *  *  *  *   *  *  *  *  *  *  *  *  *  *
  19. sequence([0, 0, 0, 0, 0, 0, 0, 0, 0, 0])
  20. #10       *  *  *  *  *  *  *  *  *  *
  22. sequence([0, 0, 0, 0, 0, 0, 0, 0, 0, 1])
  23. #10       *  *  *  *  *  *  *  *  *  *
  25. sequence([1, 0, 0, 0, 0, 0, 0, 0, 0, 1])
  26. #9           *  *  *  *  *  *  *  *  *
  28. sequence([1, 1, 0, 0, 0, 0, 0, 0, 0, 1])
  29. #9        *  *  *  *  *  *  *  *  *
  31. sequence([1, 1, 1, 0, 0, 0, 0, 0, 0, 2])
  32. #9        *  *  *  *  *  *  *  *  *

refactoring the code

This is the exact same logic as above but tests have been combined, intermediate variables removed, etc.

  1. from itertools import groupby
  3. def sequence(lst):
  4.     max_len = prev_len = running_len = 0
  5.     prev = float(&#39;nan&#39;)
  6.     decreasing = False
  7.     for k, g in groupby(lst):
  8.         if k &lt; prev:
  9.             decreasing = True
  10.         elif decreasing:
  11.             max_len = max(max_len, running_len)
  12.             running_len = prev_len
  13.             decreasing = False
  14.         prev = k
  15.         prev_len = len(list(g))
  16.         running_len += prev_len
  18.     return max(max_len, running_len)

huangapple
  • 本文由 发表于 2023年2月6日 05:40:18
  • 转载请务必保留本文链接：https://go.coder-hub.com/75355712.html
  • algorithm
  • python
  • time-complexity
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定