Somme divisible par n

Question

C'est un problème du cours Introduction aux algorithmes :

Vous avez un tableau avec n des nombres entiers positifs aléatoires (le tableau n'est pas pas besoin d'être trié ou que les éléments soient uniques). Proposez un O(n) algorithme pour trouver la plus grande somme d'éléments, qui est divisible par n .

Il est relativement facile de le trouver dans O(n 2 ) en utilisant la programmation dynamique et en stockant la plus grande somme avec le reste 0, 1, 2,..., n - 1. Ceci est un code 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];
}

Il est également facile de le trouver dans O(n) pour les éléments contigus, en stockant les sommes partielles MOD n. Autre exemple :

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;
}

Mais qu'en est-il O(n) dans le cas général ? Toute suggestion sera appréciée ! Je pense que cela a quelque chose à voir avec l'algèbre linéaire, mais je ne sais pas exactement quoi.

EDIT : Est-ce que cela peut être fait dans O(n log n) ?

Answer 1

Puisque vous ne spécifiez pas ce que au hasard (uniforme ? si oui dans quel intervalle ?) la seule solution générale est celle pour les tableaux arbitraires et je ne pense pas que vous puissiez obtenir mieux que O(n 2 ). C'est l'algorithme de programmation dynamique en 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]

Vous pouvez probablement trouver une solution plus rapide si vous avez une limite supérieure pour les valeurs dans le tableau, par ex. n .

Answer 2

Question très intéressante ! Voici mon code JS. Je ne pense pas que O(n^2) puisse être abaissé, donc je suppose que le moyen est de trouver un algorithme plus efficace en termes de benchmarking.

Mon approche (corrigée) se résume à explorer des chemins de sommes jusqu'à ce que la prochaine somme correspondante (c'est-à-dire divisible par _n) soit calculée. Le tableau source se réduit progressivement au fur et à mesure que les sommes suivantes sont trouvées.

(J'ai fourni différents exemples en haut de la page)

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 );