字符串中最长的之字形子序列

Question

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

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

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

或

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

输入:

8
10 22 9 33 49 50 31 60

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

输出:

解释:

子序列 {10, 22, 9, 33, 31, 60} 的格式为 x1 < x2 > x3 < x4 > x5 < x6 即 { 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)

Answer 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

Answer 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)，因为它只遍历列表一次。
Space 复杂度：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))

字符串中最长的之字形子序列

Longest zig-zag subsequence in a string

python

zigzag

编辑 #1