Summe durch n teilbar

Question

Dies ist ein Problem von Einführungskurs Algorithmen:

Sie haben ein Array mit n zufälligen positiven ganzen Zahlen (das Array nicht oder die Elemente einzigartig sortiert werden muß) . Schlagen Sie einen O (n) Algorithmus vor, um die größte Summe von Elementen zu finden, die durch n teilbar ist.

Es ist relativ einfach, es in O (n) mit dynamischer Programmierung zu finden und zu speichern größte Summe mit Rest 0, 1, 2, ..., n - 1. Dies ist ein JavaScript-Code :

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

es ist auch einfach in O (n) für zusammenhängende Elemente zu finden, die Teilsumme MOD n zu speichern. Ein weiteres Beispiel:

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

Aber wie O (n) im allgemeinen Fall? Irgendwelche Vorschläge werden geschätzt! Ich denke, das hat etwas mit linearer Algebra zu tun, aber ich bin mir nicht sicher, was genau.

EDIT: Kann dies tatsächlich in O (n log n) getan werden?

Answer 1

Da Sie nicht angeben, was Zufall Mittel (Uniform? Wenn ja in welchem ​​Intervall?) Die einzige allgemeine Lösung ist die, für beliebige Anordnungen und ich glaube nicht, dass Sie besser als O bekommen (n). Dies ist die dynamische Programmierung Algorithmus in 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] 

Sie können sich wahrscheinlich eine schnellere Lösung arbeiten, wenn Sie eine Obergrenze für die Werte im Array, z.B. n.

Answer 2

Sehr interessante Frage! Das ist mein JS-Code. Ich glaube nicht, dass O (n^2) gesenkt werden kann, daher denke ich, dass der Weg dahin liegt, einen Algorithmus zu finden, der im Hinblick auf das Benchmarking effizienter ist.

Mein (korrigierter) Ansatz läuft darauf hinaus, Pfade von Summen zu untersuchen, bis der nächste passende (d. H. Teilbar durch _n) berechnet ist. Das Quell-Array schrumpft fortschreitend, wenn die nächsten Summen gefunden werden.

(I bereitgestellt verschiedene Beispiele an der Spitze)

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