algorithm - 最大子数组和模 M

Question

我们大多数人都熟悉 maximum sum subarray problem .我遇到了这个问题的一个变体，它要求程序员输出所有子数组总和的最大值以某个数字 M 为模。

解决这个变体的天真的方法是找到所有可能的子数组和(这将是 N^2 的数量级，其中 N 是数组的大小)。当然，这还不够好。问题是——我们怎样才能做得更好？

示例:让我们考虑以下数组:

6 6 11 15 12 1

让 M = 13。在这种情况下，子数组 6 6(或 12 或 6 6 11 15 或 11 15 12)将产生最大总和 ( = 12 )。

Answer 1

我们可以这样做:

维护数组 sum在索引 ith , 它包含从 0 到 ith 的模数和.

对于每个索引 ith ，我们需要找到以该索引结尾的最大子和:

对于每个子数组(start + 1 , i )，我们知道这个子数组的模和是

int a = (sum[i] - sum[start] + M) % M

所以，我们只能实现大于sum[i]的子和如果sum[start]大于 sum[i]并且接近 sum[i]尽可能。

如果您使用二叉搜索树，这可以很容易地完成。

伪代码:

int[] sum;
sum[0] = A[0];
Tree tree;
tree.add(sum[0]);
int result = sum[0];
for(int i = 1; i < n; i++){
    sum[i] = sum[i - 1] + A[i];
    sum[i] %= M;
    int a = tree.getMinimumValueLargerThan(sum[i]);
    result = max((sum[i] - a + M) % M, result);
    tree.add(sum[i]);
}
print result;

时间复杂度:O(n log n)