сумма делится на п

Question

Это проблема с Введение в алгоритмы конечно:

У вас есть массив с п случайных положительных целых чисел (массив не нужно сортировать или элементы уникальны) , Предложите O (n) алгоритм найти самую большую сумму элементов, которая делится на n.

Это относительно легко найти его в O (N 2 ) с использованием динамического программирования и хранения наибольшую сумму с остатком 0, 1, 2, ..., п - 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 п. Другой пример:

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 (п) в общем случае? Любые предложения будут оценены! Я считаю, что это имеет дело с линейной алгеброй, но я не уверен, что именно.

EDIT: Может ли это быть сделано в O (n log n)?

Answer 1

Поскольку вы не указали, что случайное означает (равномерное? Если это так, в каком интервале?) Единственное общее решение - это решение для произвольных массивов, и я не думаю, что вы можете получить лучше, чем 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.

Answer 2

Очень интересный вопрос! Это мой код JS. Я не думаю, что O (n^2) можно опустить, поэтому я полагаю, что путь заключается в том, чтобы найти алгоритм, более эффективный с точки зрения бенчмаркинга.

Подход (исправленный) сводится к изучению путей сумм до тех пор, пока не будет вычислен следующий соответствующий ему (т. Е. Делимый на _n). Исходный массив постепенно сжимается по мере нахождения следующих сумм.

(я представил различные примеры в верхней части)

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