0

如何优化我为这个问题编写的以下代码？我能得到一些建议吗？

给定一个整数元素数组，找到最长子序列的长度，使得所有元素都是交替的。如果序列 {x1, x2, .. xn} 是交替序列，则其元素满足以下关系之一：

x1 < x2 > x3 < x4 > x5 < …. xn

或者

x1 > x2 < x3 > x4 < x5 > …. xn

输入：

8
10 22 9 33 49 50 31 60

其中：第一行表示数组中元素的数量。第二行代表数组元素。

输出：

6

说明：

子序列{10, 22, 9, 33, 31, 60} 的格式为x1 < x2 > x3 < x4 > x5 < x6ie { 10 < 22 > 9 < 33 > 31 < 60 }，它是该格式中最大的，该子序列的长度为6，因此是输出6。

n = int(input())
L = []
for e in input().split():
    L.append(int(e))
count, i = 0, 0
flag = None
while i < (len(L) - 1):
    for j in range(i+1, len(L)):
        if count == 0 and flag is None:
            if (L[i] < L[j]):
                count+=1
                flag = 1
                i = j
                break
            elif (L[i] > L[j]):
                count+=1
                flag = 0
                i = j
                break
            else:
                i = j
        else:
            if (flag == 0) and (L[i] < L[j]):
                count+=1
                flag = 1
                i = j
                break
            elif (flag == 1) and (L[i] > L[j]):
                count+=1
                flag = 0
                i = j
                break
            else:
                i = j

print(count+1)
4

2 回答 2

2

您可以迭代列表，同时保留对前一个节点的引用，该节点对交替模式没有贡献。

我们首先将 prev_node 设置为列表中的第一个元素。循环从索引 1 开始并迭代到结束。对于每个值，它将值与 prev_node 进行比较。如果是交替模式，则增加 max_lenght，并更新 prev_node。

LT = -1     # Less than
GT = 1      # Greater than

max_length = 1
prev_node = L[0]       # Begin at 0
prev_compare = 0
found = 0
for i in range(1, len(L)):
    if L[i] < prev_node:
        if prev_compare != LT:
            prev_compare = LT
            found = True
    elif L[i] > prev_node:
        if prev_compare != GT:
            prev_compare = GT
            found = True
    # If an alternating node is found
    if found:
        max_length += 1
        prev_node = L[i]
        found = False

print(max_length)
  • 时间复杂度：O(n)，因为它只遍历列表一次。
  • 空间复杂度：O(1)，因为（额外的）内存使用不依赖于输入大小。

编辑#1

根据您的评论，我认为您并不真正关心代码的可读性。

我有一个与上述相同算法的简短版本（就字符数而言）。逻辑基本相同，因此性能相同。

nodes = [L[0]]
prev_compare = -1
for e in L[1:]:
    if e != nodes[-1] and (e > nodes[-1]) != prev_compare:
        prev_compare = e > nodes[-1]
        nodes += [e]

print(len(nodes))
于 2020-07-15T19:25:34.793 回答
1

您可以使用生成器执行以下检查：

  • 是否对于两个连续的数字x并且y它认为x < y,
  • 两个连续的<比较c1和是否c2是交替的，即c1 != c2.

然后您可以找到第二次检查的最长子序列True。在这里我们需要考虑到两个检查都从原始序列中消耗一个“长度单位”，即如果我们发现两个连续<的比较是交替的，这将由一个单一的指示，True但它是由两个比较生成的。而这两个比较又是由三个连续的数字产生的。所以我们可以通过添加2到最终结果来解释这一点。

这是一个代码示例：

import itertools as it
from more_itertools import pairwise

numbers = [...]  # input goes here

less_than = (x < y for x, y in pairwise(numbers))
alternating = (x != y for x, y in pairwise(less_than))
lengths = (
    sum(1 for _ in g)  # length of sub-sequence
    for k, g in it.groupby(alternating)
    if k  # check if it's an alternating sub-sequence
)
result = max(lengths, default=-1) + 2
于 2020-07-15T19:01:15.263 回答