求最长升序子序列程序的循环逻辑错误排查

你的循环逻辑核心问题 #

你的输出结果是把所有递增的元素片段都拼接在了一起，完全没找出最长的单一升序子序列，核心问题出在这几点：

• 没维护每个位置的最长子序列长度：你大概率只是遍历过程中，只要当前元素比前一个大就直接追加到结果里，根本没对比不同位置的子序列长度，自然选不出最长的那条。
• 错误重复记录元素：输出里的多个28、40就是明证——你每次遇到递增关系就把当前元素加进去，而不是更新对应位置的最优子序列，导致冗余元素堆积。
• 没追踪最长子序列的路径：你完全没记录哪条子序列是最长的，只是把所有可能的递增步骤都保留了，结果自然是一堆杂乱的元素。

正确实现思路（动态规划法） #

要输出最长升序子序列及其长度，用动态规划是最直观的方式：

1. 用dp数组，dp[i]表示以第i个元素结尾的最长升序子序列长度。
2. 用prev数组，prev[i]记录该子序列前一个元素的索引，方便后续回溯出具体序列。
3. 遍历每个元素，对比它前面的所有元素，找到能让dp[i]最大的前驱，更新dp和prev。
4. 最后找到dp数组中的最大值，对应索引，通过prev回溯得到完整序列。

修正后的代码示例 #

lista = [43, 27, 28, 40, 43, 23, 29, 47, 37, 2, 14, 14, 18, 4, 27, 36, 24, 31, 42, 29]

n = len(lista)
if n == 0:
    print("长度0，序列为空")
    exit()

# dp[i]表示以lista[i]结尾的最长升序子序列长度
dp = [1] * n
# prev[i]记录该子序列前一个元素的索引
prev = [-1] * n

for i in range(n):
    for j in range(i):
        # 严格递增判断，若允许非严格则改成lista[j] <= lista[i]
        if lista[j] < lista[i] and dp[j] + 1 > dp[i]:
            dp[i] = dp[j] + 1
            prev[i] = j

# 找到最长长度和对应的索引
max_len = max(dp)
max_index = dp.index(max_len)

# 回溯得到序列
lis = []
while max_index != -1:
    lis.append(lista[max_index])
    max_index = prev[max_index]
# 回溯是从后往前，反转得到正序
lis.reverse()

print(f"最长长度{max_len}，对应序列{lis}")

运行这段代码，输出就是你预期的：最长长度4，对应序列[27, 28, 40, 43]

补充说明 #

如果需要支持非严格递增（相同元素也算入子序列），只需要把判断条件里的lista[j] < lista[i]改成lista[j] <= lista[i]即可。

内容的提问来源于stack exchange，提问作者Ed S