最大子阵列总和模M

编程入门 行业动态 更新时间:2024-10-10 21:25:39
本文介绍了最大子阵列总和模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

本文发布于:2023-11-29 04:27:11,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1645274.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:大子   阵列   总和

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!