Нахождение максимальной суммы смежных подмассива — другая версия

Question

Нахождение максимальной суммы смежных подмассива — другая версия

На этом форуме есть много постов, в которых можно найти наибольшую сумму смежных подмассивов. Тем не менее, небольшая вариация этой проблемы заключается в том, что подмассив должен иметь как минимум два элемента.

Например, для ввода [-2, 3, 4, -5, 9, -13, 100, -101, 7] код ниже дает 100. Но с вышеуказанным ограничением это будет 98 с подмассивом [3, 4, -5, 9 , -13, 100], Может ли кто-нибудь помочь мне сделать это? Я не мог получить правильную логику для этого.

#include<stdio.h>
int maxSubArraySum(int a[], int size)
{
int max_so_far = 0, max_ending_here = 0;
int i;
for(i = 0; i < size; i++)
{
max_ending_here = max_ending_here + a[i];
if(max_ending_here < 0)
max_ending_here = 0;
if(max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}

/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = {-2, 3, 4, -5, 9, -13, 100, -101, 7};
int n = sizeof(a)/sizeof(a[0]);
int max_sum = maxSubArraySum(a, n);
printf("Maximum contiguous sum is %d\n", max_sum);
getchar();
return 0;
}

Обновление 1:
Внес изменения в соответствии со Starrify, но я не понимаю, что я ожидаю. Это дает 183 вместо 98.

#include<stdio.h>

const int size = 9;

int maxSubArraySum(int a[])
{
int max_so_far = 0;
int i;
int max_ending_here[size];
int sum_from_here[size];

max_ending_here[0] = a[0];
//sum_from_here[0] = a[0] + a[1];

for (i = 1; i < size; i++)
{
max_ending_here[i] = max_ending_here[i-1] + a[i];
sum_from_here[i] = a[i-1] + a[i];

if (max_so_far < (max_ending_here[i] + sum_from_here[i]))
max_so_far = max_ending_here[i] + sum_from_here[i];

}

return max_so_far;
}

/*Driver program to test maxSubArraySum*/
int main()
{
int a[] = { -2, 3, 4, -5, 9, -13, 100, -101, 7 };
int n = sizeof(a) / sizeof(a[0]);
int max_sum = maxSubArraySum(a);
printf("Maximum contiguous sum is %d\n", max_sum);
getchar();
return 0;
}

3

algorithm arrays c++divide-and-conquer math

Решение

Другие решения

Вы можете решить эту проблему, используя алгоритм скользящего окна, который я реализовал Вот.

Во всех точках алгоритма мы поддерживаем следующее

Окно [вот … привет].
Сумма текущего окна.
Переменная с именем index, которая отслеживает неверный префикс в текущем окне, удаляя, что увеличит значение суммы. Таким образом, если мы удалим префикс [lo … index], тогда новое окно станет [index + 1 … hi], и сумма увеличится, поскольку [lo … index] имеет отрицательную сумму.
Сумма префикса хранится в переменной prefixSum. Он содержит сумму для интервала [lo … index].
Лучшая сумма найдена до сих пор.

инициализировать

окно = [0 … 1]
сумма = обр [0] + обр1
индекс = 0
prefixSum = arr [0]

Теперь во время каждой итерации цикла while,

Проверьте, существует ли префикс в текущем окне удаления, что увеличит значение суммы
добавьте следующее значение в списке к текущему интервалу и измените переменные окна и суммы.
Обновите переменную bestSum.

Следующие рабочий код Java реализует приведенное выше объяснение.

        int lo = 0;
int hi = 1;
int sum = arr[0] + arr[1];
int index = 0;
int prefixSum = arr[0];

int bestSum = sum;
int bestLo = 0;
int bestHi = 1;

while(true){
// Removes bad prefixes that sum to a negative value.
while(true){
if(hi-index <= 1){
break;
}
if(prefixSum<0){
sum -= prefixSum;
lo = index+1;
index++;
prefixSum = arr[index];
break;
}else{
prefixSum += arr[++index];
}
}

// Update the bestSum, bestLo and bestHi variables.
if(sum > bestSum){
bestSum = sum;
bestLo = lo;
bestHi = hi;
}

if(hi==arr.length-1){
break;
}

// Include arr[hi+1] in the current window.
sum += arr[++hi];
}
System.out.println("ANS : " + bestSum);
System.out.println("Interval : " + bestLo + " to " + bestHi);

Во всех точках алгоритма Lo + 1<= привет и на каждом шаге цикла while мы увеличиваем Привет на 1. Также ни одна переменная вот ни индекс когда-либо уменьшаться Следовательно, временная сложность линейна по размеру входных данных.

Сложность времени: O(n)

Пространственная сложность: O(1)

0

Источник

Accepted Answer

Подход:

Позволять max_ending_here быть массивом, элемент которого max_ending_here[i] обозначает максимальную сумму подмассивов (может быть пустой), которая заканчивается непосредственно перед (не включенным) индексом i, Чтобы вычислить это, используйте тот же подход, что и в вашей функции maxSubArraySum, Сложность времени O(n)и сложность пространства O(n),
Позволять sum_from_here быть массивом, элемент которого sum_from_here[i] обозначает сумму подмассива длины 2, начиная с (включенного) индекса i, что значит sum_from_here[i] = a[i] + a[i + 1], Сложность времени O(n)и сложность пространства O(n),
Переберите все действительные индексы и найдите максимальное значение max_ending_here[i] + sum_from_here[i]: это значение то, что вы ищете. Сложность времени O(n)и сложность пространства O(1),

Таким образом, общая сложность времени O(n) и сложность пространства O(n),

Этот подход распространяется на произвольную минимальную длину — не только 2, а время & космическая сложность не растет.

Ваш оригинальный инструмент в maxSubArraySum на самом деле является частным случаем вышеупомянутого подхода, в котором минимальная длина подмассива равна 0.

Редакция:

В соответствии с кодом, который вы указали в обновлении 1, я внес несколько изменений и представил правильную версию здесь:

int maxSubArraySum(int a[])
{
int max_so_far = 0;
int i;
int max_ending_here[size];
int sum_from_here[size];

max_ending_here[0] = 0;
for (i = 1; i < size - 1; i++)
{
max_ending_here[i] = max_ending_here[i - 1] + a[i - 1];
if (max_ending_here[i] < 0)
max_ending_here[i] = 0;
sum_from_here[i] = a[i] + a[i + 1];

if (max_so_far < (max_ending_here[i] + sum_from_here[i]))
max_so_far = max_ending_here[i] + sum_from_here[i];

}

return max_so_far;
}

Обратите внимание, ключ max_ending_here[i] а также sum_from_here[i] не должны пересекаться Вот пример:

-2   3   4   -5   9   -13   100   -101   7
| 3   4   -5   9 | -13   100 |
|              |
|              |
this            |
is             |
max_ending_here[5]    |
|
this
is
sum_from_here[5]

1