Алгоритм Кадане: как заодно вывести границы максимального подотрезка?
Максимальную сумму непрерывного подотрезка считаю Кадане за O(n). Но в задаче надо ещё и вывести индексы начала и конца этого подотрезка. Как аккуратно отследить границы, чтобы не сбиться, особенно когда все числа отрицательные?
2 ответа
Идея Кадане: ведём текущую сумму cur; если она ушла в минус — выгоднее начать новый отрезок с текущего элемента, чем тащить отрицательный хвост. Для границ: когда cur сбрасывается, запоминаем потенциальное начало tmp_start = i; когда обновляем глобальный максимум — фиксируем start = tmp_start, end = i.
long long best = a[0], cur = a[0];
int start = 0, end = 0, tmp = 0;
for (int i = 1; i < n; i++) {
if (cur + a[i] < a[i]) { cur = a[i]; tmp = i; } // выгоднее начать заново
else cur += a[i];
if (cur > best) { best = cur; start = tmp; end = i; }
}
Сложность O(n) время, O(1) память. Главная грабля — все числа отрицательные: инициализируй best = a[0] (а не 0!), иначе вернёшь пустой отрезок с суммой 0, которого в условии нет. И best бери long long, сумма n·10^9 переполнит int.
Тонкость со сравнением cur + a[i] < a[i]. Оно эквивалентно cur < 0, но записанное так, оно автоматически правильно ставит tmp = i ровно тогда, когда новый одиночный элемент лучше продолжения. Если же писать через cur < 0, не забудь сбрасывать cur = 0 ДО прибавления a[i], иначе после сброса начало отрезка съедет на одну позицию — классический off-by-one в восстановлении границ.