综上所述用n整除

Question

这是从算法导论课程的一个问题：

您有n个随机正整数数组（数组不需要进行排序或元素唯一的）。建议为O（n）算法来找到元素的最大的一笔，那就是用n整除。

这是比较容易找到它的O（n2）的使用动态编程和存储与余数为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），用于连续元素，存储部分和模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

既然你不指定哪些随机方式（统一？如果是的话在什么区间？），一般只解决方案是一个任意阵列，我不认为你可以得到任何比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]

你也许可以制定出一个更快的解决方案，如果您对数组中的值的上限，例如ñ。

Answer 2

非常有趣的问题！这是我的JS代码。我不认为这为O（n ^ 2）可以降低，因此我假设的办法是找到一个算法是在基准方面更为有效。

我的（校正）方法可以归结为探索和的路径，直到下一个匹配一个（即由_n整除）被计算。如接下来总和被发现源阵列逐渐收缩。

（I在顶部提供不同的例子）

var _a = [1000, 1000, 1000, 1000, 1000, 1000, 99, 10, 9] ;
//var _a = [1000, 1000, 1000, 1000, 1000, 1000, 99, 10, 9, 11] ;
//var _a = [1, 6, 6, 6, 6, 6, 49] ;
//var _a = [ -1, 1, 2, 4 ] ;
//var _a = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ] ;
//var _a = [1,1,1,1,1,1] ;
var _n = _a.length, _del_indexes = [] ;
var _rec = 0, _sum = 0, _start = 0, _test = 0 ;

console.log( "input array : ", _a );
console.log( "cardinality : ", _a.length );

while( _start < _a.length )
{
    _test = 0 ;
    for( var _i = _start ; _i < _a.length ; _i++ )
    {
             _sum += _a[_i%_n] ;
             _del_indexes.push( _a[_i%_n] );
             if ( ( _sum % _n ) == 0 )
             {
                 _rec = _sum ;
                 _test = 1 ;
                 break ;
             }
    }

    if ( _test )
    {
        for( var _d = 0 ; _d < _del_indexes.length ; _d++ ) _a.splice( _a.indexOf( _del_indexes[_d] ), 1 ) ;
        _start = 0 ;
    }
    else _start++ ;

    _del_indexes = [] ;
    _sum = _rec ;
}

console.log( "Largest sum % " + _n + " is : ", _rec == 0 ? "none" : _rec );