我们大多数人都熟悉的最大总和子数组问题。我碰到这个问题的一个变体,它要求程序员输出所有子数组和的最大值模数的一些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
发布评论