Maximum SubArray

The goal of the algorithm is to find the maximum sum of contigent elements in a list

The idea is to iterate over elements from left to right keeping a running sum. At each iteration, we add the current element value and the running sum can then either be:

a) Greater than 0: in this case we continue with this running sum and we will add the future elements to this running sum (as the sum of past element will add a positive value)

b) Smaller than 0: in this case we reinitialize the sum (ie we set it to 0) and a new running sum will start again at the next element

def maxSubArray(self, nums: List[int]) -> int:
    # initialize maximum subarray as the maximum in the list
    max_subarray, curr = max(nums), 0
    
    # interate over values of the list from left to right
    for x in nums:
        curr += x # add the value to the current running sum
        max_subarray = max(max_subarray, curr) # if the new running sum is greater then store is as the max
        curr = max(0, curr) # if the running sum is smaller than 0 reinitialize it to 0
    return(max_subarray)