algorithm - 能被 n 整除的和

Question

这是算法导论课上的一道题:

You have an array with n random positive integers (the array doesn't need to be sorted or the elements unique). Suggest an O(n) algorithm to find the largest sum of elements, that is divisible by 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] + 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 log n) 中完成吗？

Answer 1

由于您没有指定 random 的含义(统一？如果是，在什么时间间隔内？)唯一的通用解决方案是针对任意数组的解决方案，我认为您无法获得更好的解决方案比 O(n²)。这是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.