Given an array of integers, find the maximum possible sum you can get from one of its contiguous subarrays. The subarray from which this sum comes must contain at least 1 element.

For inputArray = [-2, 2, 5, -11, 6], the output should be
arrayMaxConsecutiveSum2(inputArray) = 7.

The contiguous subarray that gives the maximum possible sum is [2, 5], with a sum of 7.

Guaranteed constraints:
3 ≤ inputArray.length ≤ 105,
-1000 ≤ inputArray[i] ≤ 1000.

// ———————————–

Naively this can be solved with a brute-force O(N^2) solution.

Turns out there is an algorithm called Kadane’s Algorithm that can do O(N).

The idea is, imagine we keep dragging this sticky piece of jello along the array. Say it is now touching index 2 and 4, and sum of those 3 cells is -10. Now look at cell indexed 5, we want to decide if we should move the whole jello to cell 5 or we keep dragging it to cell 5. If cell 5 is 1, then keeping the old jello will give us -9, but starting fresh will give us 1. So why not starting fresh? So curr_max will become 1, move the whole jello to cell 5 and keep marching to cell 6. So on and so forth.

def arrayMaxConsecutiveSum2(inputArray):
    curr_max = inputArray[0]
    global_max = inputArray[0]
    for i in range(1, len(inputArray)):
        curr_max = max(curr_max + inputArray[i], inputArray[i])
        if curr_max > global_max:
            global_max = curr_max
    return global_max