模M的最大子阵和

Question

我们大多数人都熟悉最大和子数组问题。我遇到了这个问题的一个变体，它要求程序员输出所有子数组和的最大值模某个数m。

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

Answer 1

我们可以这样做：

维护一个数组sum，该数组在索引ith处包含从0到ith的模和。

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

伪代码：

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）