Итак, для следующего массива, где L = 3
-5 -1 2 -3 0 -3 3
Наилучшая возможная сумма как минимум длины 3 будет равна 0, где подпоследовательность - это последние три элемента (0, -3, 3)
Как вы можете вычислить эту сумму для любого массива быстрее, чем O (NL) (эффективно O (N ^ 2), если L == 0) время?
Я считаю, что вы можете сделать это в O (n) раз, независимо от выбора, используя измененную версию алгоритма Кадане.
Чтобы увидеть, как это работает, рассмотрим случай, когда L = 0. В этом случае мы хотим найти субарм максимальной суммы исходной последовательности. Это можно решить алгоритмом Кадане, умным динамическим программированием, который работает следующим образом. Идея состоит в том, чтобы отслеживать вес субарама максимального веса, заканчивающийся как раз перед, так и сразу после каждой позиции в массиве. Какое бы ни было из этих массивов, наибольшая сумма представляет собой подмассив с максимальной суммой. Пусть исходный массив равен A и пусть массив максимальных сумм, заканчивающийся в позиции k, является массивом M. Тогда алгоритм Кадане работает следующим образом:
После того, как вы заполнили эту таблицу M, вы можете просто просмотреть ее, чтобы найти максимальное значение в целом, что дает вам вес супермассивного веса.
Но как мы адаптируем это к случаю, когда L & ne; 0? К счастью, это не так уж плохо. Посмотрите на повторение для алгоритма Кадане. Идея заключается в том, что в каждой точке мы можем либо расширить массив на один шаг, либо reset вернуться в пустой массив. Но если у нас есть нижняя граница размера нашего подмассива, мы можем думать об этом по-другому: максимальный вес подмассива длиной не менее L, заканчивающийся как раз перед позицией k + 1, формируется либо путем расширения наилучшего массива длины, по крайней мере L, который заканчивается непосредственно перед позицией k одним элементом или путем отбрасывания этого массива и принятия подмассива L-элемента, который заканчивается прямо перед позицией k. Это дает нам новую версию алгоритма Кадане, которая выглядит так:
Если мы запустим это, мы заполним значения таблиц M от L до длины массива. Максимальным значением в этом диапазоне является максимальное значение субарама суммы для подмассивов длиной не менее L.
Но это не работает в линейном времени! В частности, он работает в O (nL), так как каждая итерация вычисления должна смотреть на предыдущие элементы L массива. Однако, выполняя дополнительные предварительные вычисления, мы можем отбросить это на O (n). Идея состоит в том, что мы можем собрать таблицу, содержащую суммы элемента L, перед каждым индексом массива в O (n) времени следующим образом. Сначала суммируем первые L-элементы массива и сохраняем их как S (L). Это сумма элементов L непосредственно перед позицией L. Теперь, если мы хотим получить сумму L элементов непосредственно перед индексом L + 1, wr может сделать s, суммируя первые L-элементы массива, добавив в следующий элемент массива, а затем вычитает самый первый элемент массива. Это можно сделать в O (1) раз, вычислив S (L + 1) = S (L) + A (L) - A (0). Затем мы можем использовать подобный трюк для вычисления S (L + 2) = S (L + 1) + A (L + 1) - A (1). В более общем плане мы можем заполнить эту таблицу частичных сумм в O (n) раз, используя рекуррентность
Это выполняется в O (n) времени. Если мы предварительно вычислим эту таблицу, мы сможем найти максимальный вес подмашины длиной не менее L, используя этот повтор сверху:
Затем мы можем просто сканировать по массиву M, чтобы найти максимальное значение. Весь этот процесс выполняется в O (n) времени: нам нужно время O (n), чтобы вычислить массив S, время O (n) для вычисления массива M и время O (L) = O (n), чтобы найти максимальное значение, Он также занимает пространство O (L), так как нам нужно хранить массивы M и S.
Но мы можем добиться большего, чем это, уменьшив использование памяти до O (1)! Хитрость заключается в том, чтобы заметить, что в каждой точке нам не нужны все массивы M и S; просто последний термин. Поэтому мы можем просто сохранить последнее значение M и S, которое принимает только O (1) память. В каждой точке мы также будем отслеживать максимальное значение, которое мы видели в массиве M, поэтому нам не нужно удерживать массив M после того, как мы его заполнили. Затем он дает следующее O (n) -time, O (1) -пространственный алгоритм решения задачи:
В качестве примера, здесь прослеживается алгоритм на вашем исходном массиве с L = 3:
-5 -1 2 -3 0 -3 3
S -4 -2 -1 -6 0
M -4 -2 -1 -4 0
Best -4 -2 -1 -1 0
Таким образом, выход равен 0.
Или, в другом массиве с L = 2:
0 5 -3 -1 2 -4 -1 7 8
S 5 2 -4 1 -2 -5 6 15
M 5 2 1 3 -1 -2 6 15
Best 5 5 5 5 5 5 6 15
Таким образом, выход равен 15.
Надеюсь, это поможет! Это действительно крутая проблема!
EDIT: у меня есть реализация С++ этого алгоритма, если вы заинтересованы в поиске некоторый фактический код для решения.
Это можно сделать с помощью динамического программирования в O (n).
1.) Сохраните частичные суммы до я для каждого индекса я в массиве
2.) Сохраните индекс минимальной суммы до i
3.) Храните максимум до я для каждого индекса я в массиве, который является частичной суммой до я минус частичная сумма с индексом, определенным на шаге 2, который равен Min (Sum (k)) k <= i, имея в виду ограничение того, что подпоследовательность должна быть, по меньшей мере, длины L.
Все это можно сделать в O (n) в одном цикле.
Теперь, когда у вас есть максимальная сумма до я для каждого индекса я в массиве, вы можете определить максимальную сумму смежной подпоследовательности и конечный индекс этой подпоследовательности. Когда у вас есть индекс конца, вы можете просто идти назад, пока не достигнете этой максимальной суммы. Обе эти операции также O (n).
Пример реализации в С#:
int [] values = {-5, -1, 2, -3, 0, -3, 3};
int L = 3;
int[] sumUpTo = new int [values.Length];
int[] minUpTo = new int[values.Length];
int[] maxUpTo = new int[values.Length];
for (int i = 0; i < values.Length; i++)
{
sumUpTo[i] = values[i];
minUpTo[i] = i;
if (i > 0)
{
sumUpTo[i] += sumUpTo[i - 1];
minUpTo[i] = sumUpTo[i] < sumUpTo[i - 1] ? i : minUpTo[i - 1];
}
maxUpTo[i] = sumUpTo[i] - ((i >= L && sumUpTo[minUpTo[i - L]] < 0) ? sumUpTo[minUpTo[i - L]] : 0);
}
int maxSum = int.MinValue;
int endIndex = -1;
for (int i = L-1 ; i < values.Length; i++)
if(maxUpTo[i] > maxSum)
{
endIndex = i;
maxSum = maxUpTo[i];
}
//Now walk backwards from maxIndex until we have reached maxSum
int startIndex = endIndex;
int currentSum = values[startIndex];
while (currentSum != maxSum || (endIndex - startIndex < L-1))
{
startIndex--;
currentSum += values[startIndex];
}
Console.WriteLine("value of maximum sub sequence = {0}, element indexes {1} to {2}", maxSum, startIndex, endIndex);
Here is the JAVA version :
Note : Credit goes to @templatetypedef. That explanation is awesome.
public static int max_sum_in_subarray_of_minimum_length(int [] array, int min_length){
int running_sum=0, max_sum_up_to_here=0, max_sum=0;
int begin=0, end=0, max_start=0;
/* max_sum_up_here = sum of all elements in array up to length L */
for(int i=0;i<min_length;i++){
max_sum_up_to_here+=array[i];
}
/* running sum and max sum = max_sum_up_here */
running_sum = max_sum_up_to_here;
max_sum= running_sum;
/* Iterate through all elements starting from L i.e minimum length */
for(int i=min_length;i<array.length;i++){
/* min_sum_up_to_here = min_sum_up_to_here +
next element in array - (i-L)th element in array */
max_sum_up_to_here+=array[i]-array[i-min_length];
/* if running_sum + next element in array > max_sum_up_to here then
running_sum = running_sum + next element in array
else running_sum = max_sum_up_to_here */
if( (running_sum+array[i]) > max_sum_up_to_here ){
running_sum = running_sum+array[i];
max_start = i-min_length+1;
}else{
running_sum= max_sum_up_to_here;
}
/* if running sum > max_sum then max_sum = running sum */
if( max_sum < running_sum ){
max_sum = running_sum;
begin =max_start;
end=i;
}
}
/* max_sum gives sum of contiguous sub array of length L and begin and end gives indexes of the sub array*/
return max_sum;
}
Бесполезные случаи и определения и т.д. Мое решение является естественным. Прежде всего, помните об этом, мы ищем максимальную сумму смежного фрагмента массива целых чисел, этот фрагмент имеет больше или точно L элементов. Пусть имя A - это начальный массив. По тем же причинам, что и в алгоритме Кадане, мы рассматриваем вспомогательный массив REZ, имеющий N элементов, таких как A, REZ [i], означает максимальную сумму смежного фрагмента A, содержащую по крайней мере L элементов и заканчивающуюся точно на я -й позиции. Конечно, REZ [1], RZ [2], REZ [L-1] равны значению ZERO или -INFINITY. REZ [L] = A [1] + A [2] +... + А [L]. Для остальных значений в REZ, от i, растущего от L + 1 до N, для вычисления REZ [i] мы должны выбрать максимум между двумя случаями:
Результат для первого случая можно вычислить мгновенно с массивом частичной суммы (S [i] = A [1] + A [2] +... + A [i]), S [i] -S [II]. Результат для второго случая - REZ [i-1] + A [i]. Таким образом,
После создания REZ мы должны вычислить его максимальное значение. Рассмотрим следующий пример:
N = 7
A -5 -1 2 -3 0 -3 3
L = 3
S -5 -6 -4 -7 -7 -10 -7
REZ: -INF -INF -4
REZ [4] = max (S [4] -S [4-3], REZ [3] + A [4]) = max (-2, -7) = - 2
REZ: -INF -INF -4 -2
REZ [5] = тах (S [5] -S [5-3], REZ [4] + А [5]) = макс (-1, -2) = - 1
REZ: -INF -INF -4 -2 -1
REZ [6] = max (S [6] -S [6-3], REZ [5] + A [6]) = max (-6, -4) = - 4
REZ: -INF -INF -4 -2 -1 -4
REZ [7] = max (S [7] -S [7-3], REZ [6] + A [7]) = max (0, -1) = 0
REZ: -INF -INF -4 -2 -1 -4 0
Максимальное значение в REZ равно 0, и это ответ на всю проблему.
Надеюсь, мой английский достаточно хорош. Я ищу решение для аналогичной проблемы, когда результат должен иметь не более L последовательных элементов. Когда я понял, что описанные выше методы были фактически для решений, имеющих по крайней мере L элементов, я был очень разочарован.
Ниже представлена моя реализация Java.
public static int maxSumSubsequenceGivenLength(int[] array, int l) {
if (null == array || array.length < l) {
return -1;
}
int previousSequenceSum = 0;
for (int i = 0; i < l; i++) {
previousSequenceSum += array[i];
}
int maxSum = previousSequenceSum;
int currentSum = 0;
int startIndexFinal = 0;
int endIndexFinal = l - 1;
for (int i = l; i < array.length; i++) {
currentSum = previousSequenceSum + array[i] - array[i - l];
if (currentSum > maxSum) {
maxSum = currentSum;
endIndexFinal = i;
startIndexFinal = i - l + 1;
}
previousSequenceSum = currentSum;
}
System.out.println("start index:" + startIndexFinal + " end index: " + endIndexFinal);
return maxSum;
}