Programming Interview Questions 3: Largest Continuous Sum

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.

VN:F [1.9.11_1134]
Rating: 9.0/10 (1 vote cast)
Programming Interview Questions 3: Largest Continuous Sum, 9.0 out of 10 based on 1 rating

This entry was posted in Programming Interview. Bookmark the permalink.

5 Responses to Programming Interview Questions 3: Largest Continuous Sum

1. Levent Ozgur says:

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 )?

• Arden says:

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.

2. Kowshik says:

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.

3. Prakash says:

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]) ```

• Arden says:

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.