algorithm - 被n整除的总和

这是算法入门课程中的一个问题：
你有一个n个随机正整数的数组（这个数组没有
需要排序或元素唯一）。提出一个o（n）算法
求元素的最大和，它可以被n整除。
使用动态编程和用余数0，1，2，…，n-1存储最大和，在o（n2）中相对容易找到它。这是一个javascript代码：

function sum_mod_n(a)
{
    var n = a.length;

    var b = new Array(n);
    b.fill(-1);

    for (var i = 0; i < n; i++)
    {
        var u = a[i] % n;
        var c = b.slice();

        for (var j = 0; j < n; j++) if (b[j] > -1)
        {
            var v = (u + j) % n;
            if (b[j] + a[i] > b[v]) c[v] = b[j] + a[i];
        }

        if (c[u] == -1) c[u] = a[i];
        b = c;
    }

    return b[0];
}

对于相邻元素，在o（n）中也很容易找到它，存储mod n的部分和。另一个示例：

function cont_mod_n(a)
{
    var n = a.length;

    var b = new Array(n);
    b.fill(-1);

    b[0] = 0;

    var m = 0, s = 0;

    for (var i = 0; i < n; i++)
    {
        s += a[i];
        var u = s % n;
        if (b[u] == -1) b[u] = s;
        else if (s - b[u] > m) m = s - b[u];
    }

    return m;
}

但一般情况下O（N）如何？任何建议都将不胜感激！我认为这和线性代数有关，但我不确定具体是什么。
编辑：这实际上可以在o（n logn）中完成吗？

最佳答案

因为你没有指定什么是随机的（均匀的？如果是，在什么时间间隔？）唯一的一般解是任意数组的解，我认为没有比o（n2）更好的解了。这是python中的动态编程算法：

def sum_div(positive_integers):
    n = len(positive_integers)
    # initialise the dynamic programming state
    # the index runs on all possible reminders mod n
    # the DP values keep track of the maximum sum you can have for that reminder
    DP = [0] * n
    for positive_integer in positive_integers:
        for remainder, max_sum in list(enumerate(DP)):
            max_sum_next = max_sum + positive_integer
            remainder_next = max_sum_next % n
            if max_sum_next > DP[remainder_next]:
                DP[remainder_next] = max_sum_next
    return DP[0]

如果数组中的值有一个上限（例如n），则可能可以得出一个更快的解决方案。

关于algorithm - 被n整除的总和，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/35530263/