小编del*_*tor的帖子

这是算法课程简介中的一个问题:

你有一个n个随机正整数的数组(数组不需要排序或元素唯一).建议使用O(n)算法来找到可被n整除的最大元素总和.

使用动态编程在O(n ²)中找到它并使用余数0,1,2,...,n - 1存储最大和是相对容易的.这是一个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] + …