Largest Contiguous Subarray Sum Python Interview Question

Given an integer array, find the sum of the largest contiguous subarray within the array.

For example, if the input is [−1, −3, 5, −4, 3, −6, 9, 2], then return 11 (because of [9, 2]).

Note that if all the elements are negative, you should return 0.

p.s. this is the same as question 9.5 in Ace the Data Science Interview.

A brute-force way solution to finding the sum of the largest contiguous subarray is to compute the sum over all possible contiguous subarrays, and then return the biggest sum found.

Here's what that solution looks like:

This would have a runtime complexity of O(N^3) due to the triple-nested for-loops. However, there is no need to do multiple passes: in a single iteration of the array, if we keep track of the current sum and it ever goes below 0, there is no need to include elements in that previous subarray, and we can set the current sum to 0.

Note that if the array is all negatives, then we get a final result of 0 (by taking no elements).

While doing the single iteration through the array, we keep track of the maximum seen at every point and return that at the end: