最多K次删除的最长连续递增子序列长度算法求解咨询

核心问题回顾 #

给定整数列表和整数k，求最多删除k个元素后，能得到的最长连续递增子序列（要求子序列元素在原数组中是连续段，删除元素后剩余部分严格递增）。

动态规划核心规则 #

1. 状态定义 #

dp[i][j] 表示考虑数组前i+1个元素（即nums[0..i]），使用最多j次删除操作时，能得到的最长符合要求的子序列长度。

2. 边界条件处理 #

• 当只有第一个元素（i=0）：无论允许删除多少次（0<=j<=k），最长长度都是1（保留该元素比删除它更优）。
• 当不允许删除任何元素（j=0）：dp[i][0]等价于普通的连续递增子序列长度——若nums[i] > nums[i-1]，则dp[i][0] = dp[i-1][0] + 1；否则重置为1。

3. 状态转移逻辑 #

对于每个元素nums[i]（i>0）和每个允许的删除次数j（j>0），有两种决策：

• 删除当前元素：此时最长长度直接继承前i个元素用j次删除的结果，即dp[i][j] = dp[i-1][j]。
• 保留当前元素：需要向前寻找最近的、值小于nums[i]的元素nums[m]，计算删除m+1到i-1之间元素所需的次数（delete_used = i - m - 1）。若剩余删除次数j - delete_used >=0，则长度为dp[m][j - delete_used] + 1；若前面没有符合条件的元素，只要delete_used <=j，则长度至少为1（删除所有前面元素，保留当前元素）。

最终取两种决策的最大值作为dp[i][j]的值。

4. 结果提取 #

遍历整个dp数组，取所有值中的最大值——最优解可能出现在中间某个位置，而非必须用完所有k次删除。

Python代码实现 #

def longest_increasing_after_deletion(nums, k):
    n = len(nums)
    if n == 0:
        return 0
    
    # 初始化dp数组
    dp = [[0] * (k + 1) for _ in range(n)]
    
    # 边界：第一个元素
    for j in range(k + 1):
        dp[0][j] = 1
    
    # 边界：不允许删除的情况
    for i in range(1, n):
        dp[i][0] = dp[i-1][0] + 1 if nums[i] > nums[i-1] else 1
    
    # 填充dp数组
    for i in range(1, n):
        for j in range(1, k + 1):
            # 决策1：删除当前元素
            option_del = dp[i-1][j]
            # 决策2：保留当前元素
            option_keep = 1  # 最坏情况：删除所有前面元素，保留自己
            delete_used = 0
            # 向前寻找可衔接的元素
            for m in range(i-1, -1, -1):
                if nums[m] < nums[i]:
                    if j - delete_used >= 0:
                        option_keep = max(option_keep, dp[m][j - delete_used] + 1)
                    break
                delete_used += 1
                if delete_used > j:
                    break
            # 取两种决策的最大值
            dp[i][j] = max(option_del, option_keep)
    
    # 找出全局最大值
    return max(max(row) for row in dp)

# 测试用例1
test1_nums = [1,2,3,4,4,5,6,7,8]
test1_k = 1
print(longest_increasing_after_deletion(test1_nums, test1_k))  # 输出8

# 测试用例2
test2_nums = [1,2,3,4,5,0,5,6,7,3]
test2_k =5
print(longest_increasing_after_deletion(test2_nums, test2_k))  # 输出7

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