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)
Держите потенциально лучший стартовый индекс
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;
}
Других решений пока нет …