This is one of the most common interview practice questions. Given an array of integers (positive and negative) find the largest continuous sum.
If the array is all positive, then the result is simply the sum of all numbers. The negative numbers in the array slightly complicate things. The algorithm is, we start summing up the numbers and store in a current sum variable. After adding each element, we check whether the current sum is larger than maximum sum encountered so far. If it is, we update the maximum sum. As long as the current sum is positive, we keep adding the numbers. When the current sum becomes negative, we start with a new current sum. Because a negative current sum will only decrease the sum of a future sequence. Note that we don’t reset the current sum to 0 because the array can contain all negative integers. Then the result would be the largest negative number. The code is fairly simple and will make everything clear:
def largestContinuousSum(arr): if len(arr)==0: return maxSum=currentSum=arr[0] for num in arr[1:]: currentSum=max(currentSum+num, num) maxSum=max(currentSum, maxSum) return maxSum
The time complexity is O(N) and space complexity is O(1), which are both optimal.
Good question and solution – should we also have an edge case where every element is negative? This solution gives the element value which is closest to 0 for that array but alternatively we can also consider largest continuous sum as 0 without elements :) (so we initiate the maxsum as 0 if we value the continuous sum without elements as valid )?
Good point. I think we should clarify that with the interviewer. But most probably they’ll expect the sum to have at least 1 element.
Just adding to Arden’s post: this algorithm is called “Kadane’s algorithm” (see wikipedia). Theres also a divid & conquer technique to solve the same problem.
Same function returns maxsum, start location and end location
def largestContinuousSum(arr):
if len(arr)==0:
return
maxSum = currentSum = arr[0]
start = tstart = end = 0
for pos in range(1, len(arr)):
if(arr[pos] > currentSum + arr[pos]):
tstart = pos
currentSum = arr[pos]
else:
currentSum += arr[pos]
if(currentSum > maxSum):
maxSum = currentSum
start = tstart
end = pos
return maxSum,start,end
""" sample run """
print largestContinuousSum([-1,-3,4,-3,7])
Great solution, thanks. One of my friends actually got this exact version of the question with start and end locations, last week at on-site interview of a major tech company.