求一个子数组，其和可被一个数K整除，该子数组应是所有可能子数组之和的最大值

Question

我一直在练习算法问题，我遇到了这个问题。
给定一个数组(+VE和-VE)，我必须找到一个连续的子数组，这样，和可以被任意数K整除，并且该子数组可能是最大和。对于
a={1,2,2,1,1,1,4,5,3}和k=5，可被k整除的最大和子数组是
{2,2,1,1,4,5}，sum=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];

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

细节是非常复杂的，因为你必须寻找正确的索引，你必须关心所有的异常情况（比如什么都没有找到…)，但我想你会明白算法的概念。它的运行时间是O(n)，由于前缀sum，它应该适用于负数和正数。