未命名

假设原数组是：

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

如果一个连续区间的和为 0，就可以删除它。

由于删除以后左右拼接，可能继续形成新的零和窗口。但实际上，最终被删除的元素，可以看成若干个互不重叠的、原数组中的零和子数组。

所以问题变成：

找若干个互不重叠的零和子数组，使它们的总长度最大。

---

前缀和 + DP

定义：

prefix[i] = a[0] + ... + a[i-1]

如果：

prefix[i] == prefix[j]

那么：

a[j] + ... + a[i-1] = 0

即 [j, i-1] 是一个可以删除的区间。

令：

dp[i] = 前 i 个元素最多能删除多少个

如果 [j, i-1] 是零和区间，那么：

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

直接枚举 j 是 O(n²)。

注意：

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

所以对于相同的前缀和，只需要维护最大的：

dp[j] - j

即可做到 O(n)。

Python

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]

例子

a = [1, -1, 2, -2, 3]

print(max_deleted(a))

结果：

4

可以删除：

[1, -1]
[2, -2]

一共删除 4 个。

---

再看“删除后拼接”的情况

例如：

[1, -1, 2, -2]

先删除：

[1, -1]

剩下：

[2, -2]

再删除 [2,-2]。

最终全部删除。

我们的 DP 会直接找到两个不重叠的零和区间：

[1,-1] + [2,-2]

所以答案是 4。

时间复杂度：O(n)

空间复杂度：O(n)

如果题目的数据范围是 n ≤ 10^6，这个写法也可以继续优化内存。

---

O(n²) 的写法更直观，直接枚举每个右端点和之前所有可能的左端点。

思路

dp[i] 表示前 i 个数最多能删除多少个。

对于右端点 i，枚举 j：

• 如果 a[j:i] 的和为 0
• 那么可以删除这段
• 转移：

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

为了判断区间和是否为 0，使用前缀和：

sum(j, i-1) = prefix[i] - prefix[j]

因此只需要判断：

prefix[i] == prefix[j]

Python 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]

可以先删除：

[1, -1]

然后变成：

[2, -2]

再删除。

最终相当于删除了两个互不重叠的零和区间。

所以 DP 可以把所有最终删除的部分拆成若干个原数组中的不重叠零和区间，从而得到正确答案。

复杂度：

• 时间：O(n²)
• 空间：O(n)