На этом форуме есть много постов, в которых можно найти наибольшую сумму смежных подмассивов. Тем не менее, небольшая вариация этой проблемы заключается в том, что подмассив должен иметь как минимум два элемента.
Например, для ввода [-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;
}
Подход:
Позволять 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]
Вы можете решить эту проблему, используя алгоритм скользящего окна, который я реализовал Вот.
Во всех точках алгоритма мы поддерживаем следующее
инициализировать
Теперь во время каждой итерации цикла while,
Следующие рабочий код 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)