找到最大的降序列

Question

我对这个练习有疑问 - 我必须在数字列表中找到最大的降序序列，但我可以“跳过”数字，这会搞砸我的序列。输出是最大序列的长度。

示例：
输入：
22.155 23.252 22.586 22.450 23.372 22.228 22.087 23.091 22.190 22.140 22.057 22.123 22.359 22.190 22.140 22.523 22.384 22.384 22.305 = [22.384 22.305] 输出：
7

例子中最大的序列是：
22.155 23.252 22.586 22.450 23.372 22.228 22.087 23.091 22.190 22.140 22.057 22.123 22.359 22.190 22.140 22.523 22.384 22.488 23.201 23.050

我有一些想法，但我无法实现them/it结果证明它们是错误的。

找到所有降序序列，return最大的一个（我不知道该怎么做，我认为这不是最聪明的方法）
第二个想法很复杂，我很难解释，因为我的英语不好

找到比 mainNumber 小的数字最多的 mainNumber（这些数字必须在 mainNumber 的右侧 - 例如：
22.155 23.252 22.586 22.450 23.372 22.228 22.228 22.087 23.091 22.190 22.140 22.140 22.057 22.123 22.123 22.359 22.359 22.190 当mainNumber为22.450时你只分析：23.372、22.228、22.087等，而不是前三个
现在找到新的 mainNumber，但是你的序列是从实际的 mainNumber 开始的
重复直到没有比mainNumber小的数

这是我的代码（我知道你可能会说它很糟糕）我也不知道应该在我的 while 循环中放入什么条件，所以现在我放入 1。我知道打印的索引是错误的。

times = [22.155, 23.252, 22.586, 22.45, 23.372, 22.228, 22.087, 23.091, 22.19, 22.14, 22.057, 22.123, 22.359, 22.19, 22.14, 22.523, 22.384, 22.488, 23.201, 23.05]

best = 0
count = 0
index = 0

while 1:
    for i in range(index+1, len(times)):
        for j in range(i+1, len(times)):
            if times[j] < times[i]:
                count += 1
        if count > best:
            best = count
            index = i
        count = 0
    best = 0

    print(index)

如有任何帮助，我将不胜感激。我不知道我还能做些什么。抱歉我的英语不好。

Answer 1

对于最大的降序你可以使用两个循环

连续

times = [22.155, 23.252, 22.586, 22.45, 23.372, 22.228, 22.087, 23.091, 22.19, 22.14, 22.057, 22.123, 22.359, 22.19, 22.14, 22.523, 22.384, 22.488, 23.201, 23.05]
times_len = len(times)

best = 0
start_index = 0
end_index = 0

for i in range(times_len):
  for j in range(i + 1, times_len):
    # break previous number is bigger than current number
    if times[j] > times[j -1]:
      break
  distance = j - i
  if distance > best:
    best = distance
    start_index = i
    end_index = j

print(times[start_index:end_index])

输出

[23.091, 22.19, 22.14, 22.057]

更好的方法

您可以通过以下代码跳过访问过的数字来优化您的算法。

i = 0
while i < times_len:
  for j in range(i + 1, times_len):
    # break previous number is bigger than current number
    if times[j] > times[j -1]:
      break
  distance = j - i
  if distance > best:
    best = distance
    start_index = i
    end_index = j
    i = j         # skip numbers
  else:
    i += 1

print(times[start_index:end_index])

非连续 1

更简单的非连续

times = [22.155, 23.252, 22.586, 22.45, 23.372, 22.228, 22.087, 23.091, 22.19, 22.14, 22.057, 22.123, 22.359, 22.19, 22.14, 22.523, 22.384, 22.488, 23.201, 23.05]
times_len = len(times)

best = 0
best_values = []

for i in range(times_len):
  values = [times[i]]
  for j in range(i + 1, times_len):
    if values[-1] > times[j]:
      values.append(times[j])
      
  if len(values) > best:
    best = len(values)
    best_values = values

print(best_values)

输出

[23.252, 22.586, 22.45, 22.228, 22.087, 22.057]

不连续 2

复杂的非连续方式。我创建了一个算法，也许有更快的方法。它以递归方式工作并与最佳值进行比较。

times = [22.155, 23.252, 22.586, 22.45, 23.372, 22.228, 22.087, 23.091, 22.19, 22.14, 22.057, 22.123, 22.359, 22.19, 22.14, 22.523, 22.384, 22.488, 23.201, 23.05]
times_len = len(times)

best = []

def search(values, j):
  best = []
  while j < times_len:
    if values[-1] >= times[j]:
      copy_values = values.copy()
      copy_values.append(times[j])
      result = search(copy_values, j + 1)
      if len(result) > len(best):
        best = result
    else:
      # remove lower values and start a new list
      for k in range(len(values) - 2, 0, -1):
        if values[k] >= times[j]:
          sub_values = values[:k]
          sub_values.append(times[j])
          result = search(sub_values, j + 1)
          if len(result) > len(best):
            best = result
          break
    j += 1
    
  if len(values) > len(best):
    best = values
  return best
    

for i in range(times_len):
  values = search([times[i]], i + 1)
  if len(values) > len(best):
    best = values

print(best)

输出

[23.252, 22.586, 22.45, 22.228, 22.19, 22.14, 22.057]

找到最大的降序列

Find the biggest descending sequence

python

sequence

连续

更好的方法

非连续 1

不连续 2