Kadane's Algorithm

LeetCode 53 · View on LeetCode

Track the maximum subarray sum ending at each position. At each step, either extend the current subarray or start fresh from the current element.

def max_subarray(nums: list[int]) -> int:
    current = result = nums[0]
    for num in nums[1:]:
        current = max(num, current + num)
        result = max(result, current)
    return result

if __name__ == '__main__':
    print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4]))  # 6
    print(max_subarray([1]))                                 # 1
    print(max_subarray([5, 4, -1, 7, 8]))                   # 23