Как найти максимальную сумму подпоследовательности максимальной длины

Question

Я работаю над вопросом интервью, для которого я не мог найти решение для учебников. Учитывая список целых чисел, найдите максимальную сумму любых последовательных значений/sublist не более, чем заданная длина K.

Answer 1

Пусть p [i] - префикс sum a [0] + ... + a [i - 1]. Мы можем легко вычислить последовательность p в линейном времени. Для фиксированного индекса i максимальная сумма подматрицы размером не более K, которая имеет свою правую границу при индексе i, может быть вычислена как

MAX (j = max (0, i - K + 1) to i, p [i + 1] - p [j]) = p [i + 1] - MIN (j = max (0, i - K + 1) до i, p [j])

Мы можем обрабатывать возможные правые границы i в порядке возрастания. Затем мы хотим вычислить для каждого такого i член MIN в приведенной выше формуле в O (1). Это точно проблема sliding window minimum, которая имеет приятное решение, используя специальную структуру данных очереди. Эта очередь поддерживает операции push/pop а также мин в амортизированном виде O (1). Используя этот алгоритм, наш алгоритм выглядит так:

q = new MinQueue() 
sum = 0 
answer = 0 
for i := 0 to N - 1: 
    q.push(sum) # sum == p[i] 
    if len(q) > K: 
     q.pop() 
    sum += a[i] 
    answer = max(answer, sum - q.min()) # sum == p[i + 1] 

Общая продолжительность выполнения линейна.

Answer 2

Вот контур. У вас есть X [i, где i = 1..N] числа. Учитывая K, предполагая K < = N, существуют N-K + 1 подпоследовательности, начиная с 1 .. (N-K + 1). Вы можете хранить суммы в S [j, j = 1..N-K + 1]

Скажите, у вас уже есть S [j]. Затем S [j + 1] = S [j] - X [j-1] + X [j + K-1]. Вам нужно найти S [1], а затем все просто. Теперь проблема сводится к поиску наибольшего значения в S. Возможны 1 или более ответов. Сложность линейная.

HTH, вы начнете.

Answer 3

Он похож на проблему с максимальным подмассивом. см _http: //en.wikipedia.org/wiki/Maximum_subarray_problem_

var arr = [1,2,31,24,34,3,23,24,3,25,34,54,3,2,34]; 
var getSmallestSubSeqSum = function(arr, k){ 
    var totalLength = arr.length, index = 0, sums= []; 
    for(index=0;index < totalLength-k+1;index++) 
    { 
     sums.push(0); 
    } 

    for(var index=0; index < totalLength-k+1;index++) 
    { 
     for(var aI = 0; aI < k; aI++) 
     { 
      sums[index] += arr[index + aI]; 
     } 
    } 
    console.log('Total Length: ' + totalLength); 
    console.log('Sub Length: ' + 3);  
    console.log('sums length: ' + sums.length); 
    console.log("Array: "+arr); 

    index = Math.max.apply(Math, sums); 
    console.log('Max Sum: ' + index); 
    console.log("Sums: "+ sums); 

    index = sums.indexOf(index); 
    console.log("max sum sub array: " + arr.slice(index, index + k)); 
}; 

getSmallestSubSeqSum(arr, 6); 

выше фрагмент кода должен помочь это JavaScript.

Answer 4

N чисел X [0], ... X [N-1] и предполагается, что 1 < = K < = N. S [i, l] обозначает максимальную сумму подвыражения, которая начинается с i и имеет не более l длины.

Вы имеете S [i, 1] = X [i], а затем S [i, l] = MAX (S [i + 1, l-1] + X [i], X [i]), где l> = 2.

Окончательный ответ: MAX (S [i, K], где i < = N-1 и i> = 0).