最大子阵列总和模M [英] Maximum subarray sum modulo M

问题描述

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

Most of us are familiar with the maximum sum subarray problem. I came across a variant of this problem which asks the programmer to output the maximum of all subarray sums modulo some number M.

天真的办法来解决这个变种是要找到所有可能的子阵列款项（这将是N ^ 2的顺序，其中N是数组的大小）。当然，这还不够好。现在的问题是 - 我们如何能做得更好？

The naive approach to solve this variant would be to find all possible subarray sums (which would be of the order of N^2 where N is the size of the array). Of course, this is not good enough. The question is - how can we do better?

例如：让我们看看下面的数组：

Example: Let us consider the following array:

6 6 11 15 12 1

6 6 11 15 12 1

让M = 13。在这种情况下，子阵列6 6（或12或6 6 11 15或11 15 12）将产生最大总和（= 12）。

Let M = 13. In this case, subarray 6 6 (or 12 or 6 6 11 15 or 11 15 12) will yield maximum sum ( = 12 ).

推荐答案

我们能够做到这一点如下：

We can do this as follow:

维护阵列之这在指数第i ，它包含了从0模量总和第i 。

Maintaining an array sum which at index ith, it contains the modulus sum from 0 to ith.

对于每个指数第i ，我们需要找到最大的子总和，这个指数在结束：

For each index ith, we need to find the maximum sub sum that end at this index:

对于每个子阵列（启动+ 1，I），我们知道这个子阵列的模之和

For each subarray (start + 1 , i ), we know that the mod sum of this sub array is

INT A =（总和[I] - 总和[开始] + M）％M

所以，我们只能实现一个子之比总和[I] 如果之和[开始] 大比总和[I] 大，尽量靠近总和[I] 越好。

So, we can only achieve a sub-sum larger than sum[i] if sum[start] is larger than sum[i] and as close to sum[i] as possible.

这可以，如果你使用的是二叉搜索树容易。

This can be done easily if you using a binary search tree.

伪code：

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];
    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日志N）

Time complexity :O(n log n)

这篇关于最大子阵列总和模M的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！