Почему это работает
- Лучший отрезок, который кончается в индексе i, — это либо одно nums[i], либо nums[i], добавленное к лучшему отрезку, который кончается в i - 1. Других вариантов нет, поэтому одно число here несёт всё нужное слева.
- Отрезок за спиной с отрицательной суммой только уменьшает всё, что после него, поэтому отрезок начинается заново. С суммой 0 или больше он не мешает, поэтому отрезок растёт.
- Каждый отрезок где-то кончается, поэтому наибольшее here по всем индексам, которое хранит best, и есть ответ. best начинается с nums[0], а не с 0, так что массив из одних отрицательных чисел тоже получит своё наибольшее число.
Сложность
Время O(n): один проход, на каждое число постоянная работа. Память O(1): только here и best; строки на рисунке лишь показывают их историю.
дальшеТеперь реши её сам, без подсказок.
Решить на LeetCode ↗