Suma podzielna przez n

Question

Jest to problem, z Wprowadzenie do algorytmów kurs:

Masz tablicę z n losowych liczb całkowitych dodatnich (tablica nie musi być sortowane lub elementy unikalne) . Zasugeruj, aby znaleźć największą sumę elementów, która jest podzielna przez n.

Jest to stosunkowo łatwe do znalezienia go w O (n) za pomocą programowania dynamicznego i przechowywania największej sumy z pozostałą 0, 1, 2, ..., n - 1. Jest to kod 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]; 
} 

jest również łatwo znaleźć go w o (n) na przylegających do siebie elementów, przechowywanie sum częściowych mod n. Kolejna próba:

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

Ale jak o O (n) w ogólnym przypadku? Wszelkie sugestie zostaną docenione! Uważam, że ma to coś wspólnego z algebrą liniową, ale nie jestem pewien co dokładnie.
EDYCJA: Czy można to w rzeczywistości wykonać w O (n log n)?

Answer 1

Ponieważ nie określa się, co oznacza losowo oznacza (jednolite? Jeśli tak, w jakim przedziale?), Jedynym ogólnym rozwiązaniem jest to, że dla arbitralnych macierzy i nie sądzę, że można uzyskać coś lepszego niż O (n). Jest to dynamiczny algorytm programowania w Pythonie:

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] 

Prawdopodobnie można wypracować szybsze rozwiązanie, jeśli masz górną granicę dla wartości w tablicy, na przykład n.

Answer 2

Bardzo interesujące pytanie! To jest mój kod JS. Nie sądzę, żeby O (n^2) można było obniżyć, dlatego przypuszczam, że sposobem jest znalezienie algorytmu, który byłby bardziej wydajny pod względem porównywania.

Moje (poprawione) podejście sprowadza się do zbadania ścieżek sum, dopóki nie zostanie obliczona następna pasująca (tzn. Podzielna przez _n). Tablica źródłowa stopniowo się kurczy, gdy zostaną znalezione kolejne sumy.

(I umieszczono różne przykłady z góry)

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