Макс SubArray Кадане Альгортим

void kadane(int A[], int N, int& bestStart, int& bestEnd, int& bestSum)
{

int max_ending_here = 0;
int max_so_far = 0;
bestStart = 0;for (int i = 0; i < N; i++)
{

max_ending_here += A[i];

if (max_ending_here < 0)
{
max_ending_here = 0;
}
if (max_ending_here > max_so_far)
{
max_so_far = max_ending_here;
bestEnd = i;
}

}
}

Я хочу обновить лучший стартовый индекс
Если у меня есть массив A = {- 1, -2,5,0,1}
Лучший старт должен быть индексом 2 и индексом наилучшего конца 4 Я получаю лучший результат, но я не знаю, как обновить лучший старт
Макс подмассива здесь = 6 (5 + 0 + 1)

1

Решение

Держите потенциально лучший стартовый индекс

bestStartCandidate = 0;

if (max_ending_here < 0)
{
max_ending_here = 0;
bestStartCandidate = i + 1;
}
if (max_ending_here > max_so_far)
{
max_so_far = max_ending_here;
bestStart = bestStartCandidate;
bestEnd = i;
}
0

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

Других решений пока нет …

По вопросам рекламы [email protected]