Problem Statement:
Given an array of integers, find the contiguous subarray (containing at least one number) which has the largest sum and return its sum.
Solution:
def max_subarray_sum(nums):
"""
Kadane's algo: past should add something positive else leave it!
Naive: O(n**2)
"""
max_sum = current_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum