algorithm - 找到一个子数组，其总和可以被数字 K 整除该子数组应该是所有可能子数组的最大总和

Question

我一直在练习算法题，遇到了这道题。
给定一个数组(+ve 和 -ve)数字，我必须找到一个连续的子数组，使得总和可以被任何数字 K 整除，并且子数组应该具有可能的最大总和。例如。
a={1,2,2,1,1,4,5,3} 和 k=5 可被 k 整除的子数组的最大和为
{2,2,1,1,4,5}，总和 = 15
目前我能想到的是，每个元素都有两种可能性，要么包含在目标子数组中，要么不包含。但这将是一个指数算法。
编辑:是否有可能在线性时间内解决这个问题。请帮忙

Answer 1

这道题的关键词是前缀和。

计算它们的伪代码如下所示:

int prefix_sum[N];
prefix_sum[0] = array[0];
for (i = 1; i < n; i++)
    prefix_sum[i] = prefix_sum[i-1] + array[i];

现在我们有了前缀和，剩下的就是找到子数组了。我们可以通过从最后一个子数组中减去(之前的)第一个前缀和值来查看子数组的总和。

我们关心的属性是总和和被 K 整除的能力。现在要找到最大总和子数组，我们对每个元素查看一次。当我们查看每个元素一次时，我们会做 4 件事:

1. 除以前缀和模 K:rem[i] = prefix_sum[i] % K;。这样我们就知道当且仅当 rem[start_subarray] + rem[end_subarray] == K 时，子数组才有效。但我们不仅用它来检查子数组是否可整除，不，我们还可以用它来查找子数组(见下文)。

2. 我们使用大小为 K 的数组 max_start。当我们计算 prefix_sum[i] 的余数时，我们将索引 i 存储在 max_start[rem[i]] 中，当 prefix_sum[i]大于 max_start[rem[i]] 中当前索引的 prefix_sum。现在我们能够在 O(1) 中查找具有最大前缀和且具有给定余数的索引。

3. 对于我们的元素 array[i]，我们查看 rem[i] 并查找具有最大 prefix_sum 且余数为 的元素>K-rem[i]。当我们这样做时，我们得到 a) 可被 K 整除且 b) 具有最大总和的子数组(对于所有以此元素 array[i] 结尾的数组)。

4. 我们检查这个数组的总和是否大于我们当前找到的最大数组，何时将这个数组设置为我们新的最佳得分手。

细节非常繁琐，因为您必须寻找正确的索引，并且必须处理所有异常情况(比如什么都没找到...)，但我想您会了解算法的概念.这个的运行时间是 O(n)，并且由于前缀和它应该适用于负数和正数。