Код Middle Динамическое программирование обновлено
Максимальная сумма подмассива
Условие
Наибольшая сумма непустого непрерывного подмассива (алгоритм Кадане).
Примеры
maxSubArray([-2, 1, -3, 4, -1, 2, 1, -5, 4]) // 6
maxSubArray([-1]) // -1
maxSubArray([5, 4, -1, 7, 8]) // 23
Как подойти
Кадане: cur = max(nums[i], cur + nums[i]), best = max(best, cur). Инициализация нулём - самая частая ошибка: на массиве из одних отрицательных вернёт 0 вместо максимального элемента.
Подсказки: 2
- На каждом шаге решай: продолжить текущий подмассив или начать новый с этого элемента.
- Инициализируй ответ первым элементом, а не нулём - иначе сломаешься на всех отрицательных.
Решите в тренажёре
Редактор с автотестами прямо в браузере. Можно решить спокойно, вслух или под таймером, как на собесе.