Find the max possible sum from all contiguous subarrays of a given array

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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s