Учитывая массив, найдите наибольшую сумму непрерывного подмножества. Например, ввод может быть [3, 5, -9, 1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1, -5, 4], а вывод должен быть 19 потому что непрерывное подмножество с наибольшей суммой равно [1, 3, -2, 3, 4, 7, 2, -9, 6, 3, 1]
Итак, концептуально, каков наилучший подход к решению этой проблемы? Нам нужно создать функцию, которая выполняет итерацию по каждому отдельному элементу и содержит как текущую промежуточную сумму, так и общую максимальную промежуточную сумму. Назовем текущий промежуточный итог maxEndingHere, а общий максимум maxSoFar. Чтобы максимизировать maxEndingHere в каждой итерации, нам нужно проверить, должно ли maxEndingHere быть равным текущему числу или текущему числу плюс предыдущему maxEndingHere. Другими словами, в каждой итерации maxEndingHere = Math.max(num, maxEndingHere + num) . Чтобы отслеживать общий максимум, мы также должны обновлять maxSoFar на каждой итерации. Он обновляется, когда maxEndingHere > maxSoFar или мы можем написать maxSoFar = Math.max(maxEndingHere, maxSoFar) .
Общее решение будет выглядеть так:
С точки зрения пространственно-временной сложности это выполняется за время O(n) и пространство O(1).
