Почему это работает
- Лучший отрезок либо лежит внутри массива — его как hi находит обычный алгоритм Кадане, — либо идёт через край. Тогда оставшиеся числа образуют отрезок в середине, и чтобы взятая часть была наибольшей, оставшийся отрезок должен быть наименьшим: total - lo.
- Наименьший отрезок ищется так же, как наибольший, только через min вместо max, в том же проходе.
- Если все числа отрицательные, наименьший отрезок — всё кольцо, и total - lo = 0 означает «не брать ничего», а так нельзя. Тогда возвращаем hi — наибольшее отдельное число.
Сложность
Время O(n): один проход, каждое число обновляет пять значений. Память O(1): пять чисел; строки на рисунке показывают их историю.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗