Это неправильная реализация алгоритма Кадане?
#include <iostream>
#include <limits>
int MIN = std::numeric_limits<int>::min()
using namespace std ;
void findMaxSubArray(int inputArray[] , int n )
{
int maxStartIndex=0;
int maxEndIndex=0;
int maxSum = MIN ;
int cumulativeSum= 0;
int maxStartIndexUntilNow=0;
for (int currentIndex = 0; currentIndex < n ; currentIndex++)
{
int eachArrayItem = inputArray[currentIndex];
cumulativeSum+=eachArrayItem;
if(cumulativeSum>maxSum)
{
maxSum = cumulativeSum;
maxStartIndex=maxStartIndexUntilNow;
maxEndIndex = currentIndex;
}
else if (cumulativeSum<0)
{
maxStartIndexUntilNow=currentIndex+1;
cumulativeSum=0;
}
}
cout << "Max sum : "<< maxSum << "\n" ;
cout << "Max start index : "<< maxStartIndex << "\n" ;
cout << "Max end index : "<< maxEndIndex << "\n" ;
}
int main()
{
int intArr[] = {-1,3,-1,-1,-1,-1,-1,-1 } ;
//int intArr[] = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
//int intArr[]={-6,-2,-3,-4,-1,-5,-5};
findMaxSubArray(intArr,8);
return 0 ;
}
Я скептически относился к тому, была ли дана реализация Вот было правильно или нет, поэтому я реализовал это точно в C ++, и для приведенного выше теста это не работает. Я не могу узнать, где алгоритм неверен?
Решение
принимать
int maxSum = -1; решит вашу проблему
также ваша вышеуказанная программа не компилируется.
Это работает для integer чисел
#include <iostream>
#include <limits>
using namespace std ;
int MIN = std::numeric_limits<int>::min();
void findMaxSubArray(int inputArray[] , int n )
{
int maxStartIndex=0;
int maxEndIndex=0;
int maxSum = -1 ;
int cumulativeSum= 0;
int maxStartIndexUntilNow=0;
for (int currentIndex = 0; currentIndex < n ; currentIndex++)
{
int eachArrayItem = inputArray[currentIndex];
cumulativeSum+=eachArrayItem;
if(cumulativeSum>maxSum)
{
maxSum = cumulativeSum;
maxStartIndex=maxStartIndexUntilNow;
maxEndIndex = currentIndex;
}
else if (cumulativeSum<0)
{
maxStartIndexUntilNow=currentIndex+1;
cumulativeSum=0;
}
}
cout<< "Max sum : "<< maxSum << "\n" ;
cout<< "Max start index : "<< maxStartIndex << "\n" ;
cout<< "Max end index : "<< maxEndIndex << "\n" ;
}
int main()
{
int intArr[] = {-1,3,-1,-1,-1,-1,-1,-1 } ;
//int intArr[] = {-1, 3, -5, 4, 6, -1, 2, -7, 13, -3};
//int intArr[]={-6,-2,-3,-4,-1,-5,-5};
findMaxSubArray(intArr,8);
return 0 ;
}
Другие решения
int maxStartIndex=0;
int maxEndIndex=0;
int maxSum = MIN;
Это твоя проблема. Вы лжете по алгоритму. Подмассив, который начинается и заканчивается в индексе 0, имеет сумму arr[0], не отрицательная бесконечность. Но это тоже не очень хорошая отправная точка.
int maxStartIndex=0;
int maxEndIndex=-1;
int maxSum = 0;
Любой массив имеет подмассив с нулевой суммой: пустой. Тебе нужно выиграть, а не любую отрицательную сумму.
В общем, есть много хороших ресурсов. Вот ссылка на полезный ресурс, который вы должны посмотреть на C ++. Вы также можете посмотреть на этот ресурс, из которого происходит приведенный ниже код и который имеет реализацию C. Вот псевдокод для грубого алгоритма:
Initialize:
max_so_far = 0
max_ending_here = 0
Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far
Вот простая программа, которая реализует алгоритм на C:
#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, -1, -2, 1, 5, -3};
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;
}
Как отметили люди, этот подход не работает для всех отрицательных чисел. Он просто возвращает 0, если все числа отрицательны. Таким образом, мы можем дополнительно оптимизировать проблему. Вот пример кода, который приятно оптимизирует оригинальный подход:
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;
/* Do not compare for all elements. Compare only
when max_ending_here > 0 */
else if (max_so_far < max_ending_here)
max_so_far = max_ending_here;
}
return max_so_far;
}
Проблема с вашим кодом заключается в том, что вы (cumulativeSum> maxSum) проверяете это раньше (Cumulative<0) и поскольку ваш maxSum равен MIN, поэтому, если первое число отрицательное, а второе положительное, оно не будет выполнено, так как cumulativeSum> maxSum, так что -1 будет добавлено к cumulativeSum, и, следовательно, ответ будет 2, а не 3. Поэтому либо проверьте (cumulativeSum<0) до или сделайте maxSum = -1 или добавьте условие в (cumulativeSum> maxSum && совокупная сумма> 0)