algorithm - 带消元的最大子数组

Question

我知道如何在 O(n) 中找到数组的最大连续子数组。然而，以下链接中的第二个问题要求在可以消除某些元素 (k) 时找到最大连续子数组： http ://www.iarcs.org.in/inoi/2011/inoi2011/inoi2011-qpaper.pdf 我似乎找不到有效的方法来做到这一点。

Answer 1

鉴于我相信做一个 O(N^2) 解决方案的约束条件。我不会告诉你如何解决这个问题，但会给你一些提示：

1. 请注意，这些数字的价值非常有限 - 它们可能只在 [-10^4, 10^4] 范围内，这使得有一个数组可以计算给定值有多少数字（总体而言数组或仅在给定的间隔内）
2. 迭代您将选择的子数组的长度，并在线性时间内解决每个长度的问题
3. 请注意，对于给定的数组，如果它们小于 k，您将始终丢弃最小的 k 值或子数组中的所有负数

希望这能帮助您解决问题。

Answer 2

有一个 O(NK) 动态规划解决方案：

让d[i][j](0<= i<=N, 0<= <=K) 是通过消除元素以第 th 个元素j结尾的任何（可能为空）子数组的最大和。ij

初始值： d[0][j] = 0对于 0<= j<=K

更新动态值：

for i = 1 to N:
     d[i][0] = max (d[i-1][0]+a[i], 0)
     for j = 1 to K:
         d[i][j] = max(d[i-1][j]+a[i], d[i-1][j-1])

解决方案是max{d[N][j]}0<= j<=K