第1题-零和区间删除

小红书9月20日机考题目与解析

（题意按回忆整理）给定数组，可以反复删除和为 0 的连续子数组——删除后左右两侧拼接，拼接产生的新零和区间可以继续删。求最多能删除多少个元素。

例如原数组：

[1, -1, 2, 3, -5, 4]

任何一个和为 0 的连续区间都可以删。

思路

关键转化：删除后左右拼接、继续删除的过程，最终效果等价于——选若干个互不重叠的、原数组中的零和子数组，使总长度最大。

以 [1, -1, 2, -2] 为例：先删 [1,-1] 剩下 [2,-2] 再删，最终全删；DP 直接找到两个不重叠零和区间 [1,-1] + [2,-2]，答案 4。

于是问题变成前缀和 + 区间 DP：

• prefix[i] = a[0] + ... + a[i-1]；prefix[i] == prefix[j] 当且仅当 [j, i-1] 是零和区间
• dp[i] = 前 i 个元素最多能删除多少个
• 若 [j, i-1] 零和：dp[i] = max(dp[i], dp[j] + (i - j))

方法一：O(n²) 直观版

枚举每个右端点和所有可能的左端点：

def max_deleted(a):
    n = len(a)

    # prefix[i] 表示前 i 个数的和
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + a[i]

    # dp[i]：前 i 个元素最多删除多少个
    dp = [0] * (n + 1)

    for i in range(1, n + 1):
        # 不删除 a[i-1]
        dp[i] = dp[i - 1]

        # 枚举最后一个被删除区间 [j, i-1]
        for j in range(i):
            # a[j:i] 的和为 0
            if prefix[i] == prefix[j]:
                dp[i] = max(dp[i], dp[j] + i - j)

    return dp[n]


# 示例
a = [1, -1, 2, -2, 3]
print(max_deleted(a))   # 4：删 [1,-1] 和 [2,-2]

方法二：O(n) 优化版

注意到转移可以变形：

dp[j] + i - j = i + (dp[j] - j)

对于相同的前缀和，只需要维护最大的 dp[j] - j，用哈希表 best[prefix_sum] 存下来，即可省掉内层枚举：

def max_deleted(a):
    n = len(a)

    # dp[i]：前 i 个元素最多删除多少个
    dp = [0] * (n + 1)

    # best[prefix_sum] = max(dp[j] - j)
    best = {0: 0}

    prefix = 0

    for i in range(1, n + 1):
        prefix += a[i - 1]

        # 不删除第 i 个元素
        dp[i] = dp[i - 1]

        # 如果之前出现过相同前缀和
        if prefix in best:
            dp[i] = max(dp[i], i + best[prefix])

        # 更新这个前缀和对应的最优值
        value = dp[i] - i
        if prefix not in best or value > best[prefix]:
            best[prefix] = value

    return dp[n]

复杂度：时间 O(n)，空间 O(n)；n ≤ 10^6 时可再把 dp 滚动成一个变量优化内存。

验证

a = [1, -1, 2, -2, 3]：删除 [1,-1] 与 [2,-2]，共 4 个元素，两种写法均输出 4。

「删除后拼接」的正确性：任何一串连锁删除，都可以按删除发生的位置还原成原数组中若干互不重叠的零和区间；反之任何一组互不重叠零和区间都能按从右到左的顺序依次删除。两者一一对应，DP 取最大总长即答案。