移除最多一个元素时寻找最长整数子序列的长度问题

问题定义 #

给定整数序列，允许最多移除一个元素，求解能得到的最长严格递增子序列的长度。

示例说明 #

• 示例1：输入 [2, 3, 4, 5, 5, 6, 4, 5]，输出5。移除索引为4的5后，可得到严格递增子序列 [2, 3, 4, 5, 6]。
• 示例2：输入 [2, 3, 4, 4, 4, 5, 6, 7]，按严格递增子序列计算输出应为6（对应[2, 3, 4, 5, 6, 7]），推测原示例描述可能混淆了子序列与连续子数组；若需求为最长连续严格递增子序列，输出才为4（对应[4,5,6,7]）。

核心解法思路 #

通过预处理两个辅助数组，快速计算移除任意元素后的最长递增子序列长度：

1. left数组：left[i]表示以第i个元素结尾的严格递增子序列长度（无元素移除）。
2. right数组：right[i]表示以第i个元素开头的严格递增子序列长度（无元素移除）。

遍历每个位置时，计算两种情况的最大值：

• 不移除任何元素：取left数组的最大值。
• 移除第i个元素：若nums[i-1] < nums[i+1]，则可拼接left[i-1]与right[i+1]；边界元素直接取另一侧的子序列长度。

具体实现步骤 #

1. 计算left数组 #

从左到右遍历序列，对每个元素nums[i]，遍历其左侧所有元素，若nums[j] < nums[i]，则更新left[i] = max(left[i], left[j]+1)。

2. 计算right数组 #

从右到左遍历序列，对每个元素nums[i]，遍历其右侧所有元素，若nums[i] < nums[j]，则更新right[i] = max(right[i], right[j]+1)。

3. 计算最终结果 #

初始化结果为left数组的最大值（对应不移除元素的情况），再遍历每个位置，计算移除该元素后的可能最长长度，更新结果的最大值。

Python代码实现 #

def longest_strictly_increasing_after_remove(nums):
    n = len(nums)
    if n <= 2:
        return n
    
    # 计算left数组：以i结尾的最长严格递增子序列长度
    left = [1] * n
    for i in range(1, n):
        for j in range(i):
            if nums[j] < nums[i]:
                left[i] = max(left[i], left[j] + 1)
    
    # 计算right数组：以i开头的最长严格递增子序列长度
    right = [1] * n
    for i in range(n-2, -1, -1):
        for j in range(i+1, n):
            if nums[i] < nums[j]:
                right[i] = max(right[i], right[j] + 1)
    
    max_length = max(left)  # 不移除元素的情况
    
    # 遍历每个可能被移除的元素
    for i in range(n):
        if i == 0:
            current = right[1]
        elif i == n-1:
            current = left[n-2]
        else:
            if nums[i-1] < nums[i+1]:
                current = left[i-1] + right[i+1]
            else:
                current = max(left[i-1], right[i+1])
        max_length = max(max_length, current)
    
    return max_length

# 测试示例1
nums1 = [2, 3, 4, 5, 5, 6, 4, 5]
print(longest_strictly_increasing_after_remove(nums1))  # 输出5

# 测试示例2（按严格递增子序列计算）
nums2 = [2, 3, 4, 4, 4, 5, 6, 7]
print(longest_strictly_increasing_after_remove(nums2))  # 输出6

复杂度分析 #

• 时间复杂度：O(n²)，两次遍历计算left和right数组各需O(n²)，最后遍历更新结果为O(n)。
• 空间复杂度：O(n)，需要存储left和right两个数组。

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