我需要一个有效的代码来查找整数列表中最长的非重叠整数序列。
我到处寻找，甚至询问了 GPT4o，但没有找到解决这个相当简单但有趣的问题的好方法。
如果有人可以帮助我改进它并检查它的准确性，我真的很感激！
提前致谢。
这是我到目前为止所得到的。这是非常低效和缓慢的，但它似乎工作正常。
import math
from collections import Counter
seq = [1, 2, 3, 1, 2, 6, 1, 2, 3]
#seq = [0, 0, 0, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 2, 3]
#seq = [-2, 2, -2, 2, -2, 2, -2, 2, -2, 2, -2, 2, -2, 2, -2, 2]
def count_patterns(lst, sublist):
count = 0
idx = 0
for i in range(len(lst) - len(sublist) + 1):
if lst[idx:idx + len(sublist)] == sublist:
count += 1
idx += len(sublist)
else:
idx += 1
return count
all_seqs = Counter()
max_pat_len = math.ceil(len(seq) / 2)
num_iter = 0
for i in range(len(seq)):
for j in range(i+1, len(seq)+1):
if j-i <= max_pat_len:
all_seqs[tuple(seq[i:j])] += 1
num_iter += 1
max_count = 0
max_len = 0
for val, count in all_seqs.items():
if max_len < len(val):
max_count = max(2, count)
if count > 1:
max_len = max(max_len, len(val))
pval = val
max_pats = []
for val, count in all_seqs.items():
if count == max_count and len(val) == max_len:
max_pats.append(val)
for pat in max_pats:
if count_patterns(seq, list(pat)) > 1:
print(len(pat))
print(pat)
你可以使用更有效的算法来解决这个问题。下面是一些使用动态规划的 Python 代码，以及解释算法工作原理的步骤：
def longest_repeating_non_overlapping_subsequence(seq):
"""
在整数列表中查找最长的重复非重叠整数序列。
Args:
seq: 整数列表。
Returns:
一个元组，其中包含最长重复非重叠序列的长度和列表
（如果找不到此类序列，则返回 (0, [])）。
"""
n = len(seq)
# 初始化一个表来存储最长重复子序列的长度
# seq[i:j] 和 seq[j:]
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
# 初始化最长重复子序列的长度
max_len = 0
end_index = 0
# 遍历所有可能的子序列的开始位置
for i in range(1, n + 1):
# 遍历所有可能的子序列的结束位置
for j in range(i + 1, n + 1):
# 如果子序列相同且不重叠
if seq[i - 1] == seq[j - 1] and j - i > dp[i - 1][j]:
# 更新最长重复子序列的长度
dp[i][j] = dp[i - 1][j] + 1
# 更新最长重复子序列的长度及其结束位置
if dp[i][j] > max_len:
max_len = dp[i][j]
end_index = j
# 构建最长重复子序列
longest_seq = seq[end_index - max_len:end_index] if max_len > 0 else []
return max_len, longest_seq
# 示例用法
seq = [1, 2, 3, 1, 2, 6, 1, 2, 3]
max_len, longest_seq = longest_repeating_non_overlapping_subsequence(seq)
print("最长重复子序列的长度：", max_len)
print("最长重复子序列：", longest_seq)
解释：
-
动态规划表： 该算法使用二维列表（
dp）来存储计算的中间结果。dp[i][j]存储在seq[0:i]和seq[j:n]中找到的最长重复非重叠子序列的长度，其中n是序列的长度。 -
基本情况： 该表的初始化方式是，如果
i或j为 0，则所有条目都为 0。这是因为如果其中一个子序列为空，则最长重复子序列的长度为 0。 -
迭代计算： 该算法迭代地填充
dp表，从左上角到右下角。在每个单元格dp[i][j]处，该算法会检查seq[i-1]是否等于seq[j-1]以及子序列是否不重叠 (j-i > dp[i-1][j])。如果是，则将dp[i][j]设置为dp[i-1][j] + 1。否则，将dp[i][j]设置为 0。 -
最长序列的长度：
dp表中的最大值表示最长重复非重叠子序列的长度。 -
回溯（可选）： 要找到实际的子序列，你可以从
dp表中存储最大值的单元格开始回溯，并根据用于填充该单元格的值重建该序列。
时间复杂度：
该算法的时间复杂度为 O(n^2)，其中 n 是序列的长度。这是因为我们必须填充大小为 n x n 的
dp
表。
空间复杂度：
该算法的空间复杂度也为 O(n^2)，这是因为我们必须存储大小为 n x n 的
dp
表。但是，如果我们只需要最长序列的长度，则可以将空间复杂度降低到 O(n)，因为我们只需要存储
dp
表的上一行。