长度为k的递增子序列最大和问题的DP实现错误及优化咨询

原有动态规划的状态定义存在信息丢失问题。单个下标位置可以对应多个不同长度的递增子序列，原有方案仅保留了该位置结尾的最大和子序列对应的长度，直接丢弃了该位置更短长度的合法子序列信息。例如输入中的13，除了长度为2和为17的子序列[4,13]外，还存在长度为1和为13的子序列[13]，后者正是计算14结尾的长度为2的子序列时需要的合法前驱，却被原有逻辑丢弃了。

将一维DP状态扩展为二维状态：

• 定义dp[l][i]表示以第i个元素结尾，长度恰好为l的递增子序列的最大和
• 边界条件：长度为1的子序列和就是元素本身，即dp[1][i] = input[i]
• 状态转移：对于长度l>=2的情况，遍历所有在i之前且值小于input[i]的元素j，取dp[l-1][j]的最大值加上input[i]作为dp[l][i]的取值

input = [4,13,5,14] 
k = 2
n = size of input
# 初始化dp数组，-infinity表示对应状态不可达
dp = 二维数组，大小为 (k+1) * n，所有值初始化为 -infinity
highest_sum = -1

# 长度为1的边界处理
FOR i in range(0, n):
    dp[1][i] = input[i]
    IF k == 1:
        highest_sum = max(highest_sum, dp[1][i])

# 填充长度从2到k的状态
FOR l in range(2, k+1):
    FOR i in range(0, n):
        max_prev_sum = -infinity
        # 找所有符合条件的前驱j
        FOR j in range(0, i):
            IF input[j] < input[i] AND dp[l-1][j] > max_prev_sum:
                max_prev_sum = dp[l-1][j]
        # 更新当前状态
        IF max_prev_sum != -infinity:
            dp[l][i] = max_prev_sum + input[i]
            IF l == k:
                highest_sum = max(highest_sum, dp[l][i])

return highest_sum

针对你给出的输入[4,13,5,14]、k=2，计算过程如下：

• 长度为1的状态：dp[1] = [4, 13, 5, 14]
• 长度为2的状态：
  • 下标1（值13）：仅前驱下标0符合条件，dp[2][1] = 4+13=17
  • 下标2（值5）：仅前驱下标0符合条件，dp[2][2] =4+5=9
  • 下标3（值14）：前驱下标0、1、2都符合条件，最大的dp[1][j]为13，dp[2][3] =13+14=27
    最终返回的highest_sum为27，符合预期结果。

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