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.22_1171]
Rating: 8.9/10 (57 votes cast)
Programming Interview Questions 3: Largest Continuous Sum, 8.9 out of 10 based on 57 ratings
This entry was posted in Programming Interview. Bookmark the permalink.
  • Levent Ozgur

    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

      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.

  • Kowshik

    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.

  • http://www.cs.ucsb.edu/~prakash Prakash

    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

      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.

      • Ilya

        For {5, -1, -2, 3, -2} this algorithm give only {5} instead of {5, -1, -2, 3} if I’m not mistaken.

      • Md

        I tried prakash algorithm, but it failed for {-40,1,40,-50,1,50,-20,1,20,0,0}
        the code returned maxSum of 52 and it should return 51. Please Correct me if i am wrong.

        • Pankaj Gakhar

          I think the correct version will be this :-

          int max_sum_subarray(int a[])

          {
          int max_sum = 0, curr_sum = 0;
          for (int i = 0; i = 0)
          curr_sum += a[i];
          else
          curr_sum = 0;
          max_sum = Math.max(curr_sum, max_sum);
          }
          return max_sum;
          }

          This gives 51 for input {-40,1,40,-50,1,50,-20,1,20,0,0}.

          • Md

            thanks for the reply but your code gives 0 for input={3,-5,2,-4,6,-9,9,-10} and I think it should return 9

          • Md

            This is the right solution. Some test cases
            {3, -5, 2, -4, 6, -9, 9, -10}; //positive negative pattern
            {-5, 4, 7, -9, 1};
            {-5, -4, -7, -9, -1}; all negative
            { 2, 3, -28, 4, 8, 1, 5, 0};
            { 5, 7, -13, 10, 5 }; //should return 15
            { 0 }; // should return 0
            {999999999}; //edge case should return 999999999
            {-40,1,40,-50,1,50,-20,1,20,0,0}
            { 2, -2, 5, -5, 6, -6 }; // should return 6
            {-40,1,40,-50,1,50,-20,1,20,0,0}; //return 51

          • christan

            for {-40,1,40,-50,1,50,-20,1,20,0,0} the algorithm should give 52, not 51. Start from the second 1:
            1+50+(-20)+1+20 = 52

          • vikas

            1 + 50 + -20 + 1 + 20 = 52

        • Himani Kapoor

          1,50,-20,1,20

    • Mahmoud

      Hi Prakash, I altered your code to handle some test cases. He it is.

      • avimas

        doesn’t work for {1, 2, 3, 4, -6, 7, 7, 7}

        see my correction:

        public static void large_cont(int[] values){

        int tstart = 0;

        int startpos = 0;

        int endpos = 0;

        int cursum = values[0];

        int maxsum = values[0];

        if(values.length > 1){

        for(int i = 1; i cursum + values[i] || values[i] > values[i]+ cursum ){

        cursum = values[i];

        tstart = i;

        }

        else{

        cursum += values[i];

        }

        if(cursum > maxsum){

        maxsum = cursum;

        startpos = tstart;

        endpos = i;

        }

        }

        }

        System.out.println(maxsum + ” ” + startpos + ” ” + endpos);

        }

  • http://none ss

    //currentSum=max(currentSum+num, num)
    maxSum=max(currentSum, maxSum)//
    Why do we need this at every iteration / parsing?

    def largestContinuousSum(arr):
    if len(arr)==0:
    return
    maxSum=currentSum=arr[0]
    for num in arr[1:]:
    if num < 0
    { maxSum=max(currentSum, maxSum)
    currentSum = 0 }
    else, currentSum += num
    return maxSum

    • Arden

      What if array is all negative numbers? Then the above algorithm will return 0 as result, which will be incorrect.

      • Anonymous

        That is debatable, 0 is a valid sum if you are allowed to select a range of length 0.

  • melih

    I know it is less efficient (but asymptotically there is no difference) but may be this one is easier to understand, at least this is the simplest solution that I come up with when I first look at the question

    def LargestContinuousSum(arr):

    if not arr:
    return

    (cumulatives, curr_sum) = ([],0)
    cumulatives.append(arr[0])
    for idx in xrange(1,len(arr)):
    cumulatives.append(cumulatives[idx-1]+arr[idx])

    (max_sum, max_idx) = (cumulatives[0], 0)
    for idx in xrange(1,len(cumulatives)):
    if cumulatives[idx] > max_sum:

    (max_sum, max_idx) = (cumulatives[idx], idx)

    (min_sum, min_idx) = (0,0)
    for idx in xrange(max_idx):
    if min_sum > cumulatives[idx]:
    (min_sum, min_idx) = (cumulatives[idx], idx)

    return max_sum-min_sum,min_idx,max_idx

  • Md

    I tried prakash algorithm, but it failed for {-40,1,40,-50,1,50,-20,1,20,0,0}
    the code returned 52 and it should return 51. Please Correct me if i am wrong.

    • Rohit

      52 is correct answer – 51 comprises only of 1 and 50..
      whereas 52 is series of 1, 50, -20, 1, 20
      in this problem you have to find the largest sum which is 52

  • http://www.facebook.com/harkirat.saluja Harkirat Saluja

    #include

    void main()
    {
    int a[5]={-1,-2,-3,-10,-7}; //enter any aray

    int i,cur,max=0;
    cur=0;

    for(i=0;imax)
    {
    max=cur;
    }
    if(cur<0)
    {
    cur=0;
    }

    }
    printf("%d",max);
    }

  • rahul

    void MaxSubSeq(int array[],int length, int *start, int *end)

    {

    long long max_sum = -(((long long)1)<<(8*sizeof(int)));

    long long entire_sum=0;

    int break_point = -1,i=0;

    for(; i<length; i++)

    {

    entire_sum += array[i];

    printf("entire_sum = %lldn",entire_sum);

    if(max_sum < entire_sum)

    {

    max_sum = entire_sum;

    printf("Max_Sum = %lld ",max_sum);

    *start = break_point+1;

    *end = i;

    printf("start %d end %d n", *start, *end);

    }

    if(entire_sum <= 0)

    {

    entire_sum = 0;

    break_point = i;

    }

    }

    }

    main () {

    //int arr[] = {1, 3, 5, -2, 6, -2, -4, -8, 2, 3, -1, -1, 4, 5, 9};

    int arr[] = {-3,-5,-2,-4,-6,-9,-1,-10};

    int s = 1, e = 7;

    MaxSubSeq(arr, 8, &s, &e);

    }

  • yoda

    /*this java code prints maximum contiguous sub array and its sum*/

    public class MaxSubArray {

    public static void maxSubArray(int[] Q){

    int A1=Integer.MIN_VALUE,A=0;

    int s=0,s1=0;

    int e=0,e1=0;

    for (int i = 0; i Q[i]+A){

    A=Q[i];

    s=i;

    e=i;

    }

    else{

    A=Q[i]+A;

    e=i;

    }

    if(A>A1){

    A1=A;

    s1=s;

    e1=e;

    }

    }

    System.out.println(“the maximum subarray sum is: “+A1);

    for (int i = s1; i <= e1; i++) {

    System.out.print(Q[i]+" ");

    }

    System.out.println();

    }

    public static void main(String[] args) {

    int[] Q={13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};

    int[] Q1={1,2,3,4,5,6,7,8,9,10};

    int[]Q2={-10,-9,-8,-7,-6,-5,-4,-3,-2,-1};

    int[] Q3={-40,1,40,-50,1,50,-20,1,20,0,0};

    maxSubArray(Q);

    maxSubArray(Q1);

    maxSubArray(Q2);

    maxSubArray(Q3);

    }

    }

    • yoda

      time complexity is O(N) and space complexity is O(1)

  • Strangevil

    /* Following code not only gives the largest sum but also gives the start and end pointer to of the contiguous array (something most interviewers ask now a days)..

    It also handles all the edge cases.. At least the start and end ones which I have tested
    */
    package DSA;

    public class largest_contiguous_sum {

    public static void sum(int a[]){
    int maxSum;
    int currentSum;
    int count=0;
    int firstpointer = 0;
    int endpointer = 0;

    /* Since we will be looping from the first element, we need to check the 0th elements value… If positive, we make it current and maxsum and also increment count… Else we make currSum and maxSum as 0 and do not increment count…

    This handles the edge case where the contiguous array is at the start
    */
    if(a[0]>0){
    currentSum = maxSum = a[0]; //boundary condition for first element
    count++;
    }else{
    currentSum = maxSum = 0;
    }

    for(int i=1; i=0){ //We change the currentSum value only if a[i] is greater than 0
    currentSum = currentSum+a[i];
    count++;
    }else{
    /*
    We check if the incoming sum of array till the previous index is greater than the max we have until this point… If it is greater, we overwrite previous value
    */
    if(currentSum > maxSum){
    maxSum = currentSum;
    firstpointer = i-count; //firstpointer will be computed by subtracting count
    endpointer = i-1;
    //end pointer will be the index before the negative number encountered
    }
    // We reset the counters and the sum
    currentSum = 0;
    count = 0;
    }
    }
    /*The above code handles all cases except 1… which is if the contiguous array is at the end (ends at a.length-1)

    In order to handle the case, we see that after the for loop ends whether there is a value in currentSum… Since we reset currentSum in the else part, this means that in the above case currentSum value won’t reset as we never go in the else part. Hence as we break outside the loop we check if the buffered value is greater than the computed maxSum… If it is then we overwrite it and output the indexes accordingly…

    That is what happens in the below in..else block
    */

    if(currentSum < maxSum){
    System.out.println(maxSum);
    System.out.println(firstpointer+" "+endpointer);
    }else{
    System.out.println(currentSum);
    System.out.println((a.length-count) +" "+ (a.length-1));
    }
    }

    public static void main(String[] args) {

    // TODO Auto-generated method stub

    int a[] = {200,33,4,-1,7,9,-2,13,91,1,-2,9,8,110};

    sum(a);

    }

    }

  • satish
  • Noah

    static int largestContinuousSum( int[] array )
    {
    var maxSum = 0;
    var currentSum = 0;
    maxSum = currentSum = array[ 0 ];

    for( int index = 1; index < array.Length; index++ )
    {
    var num = array[ index ];
    var sum = currentSum + num;
    currentSum = ( sum < currentSum ) ? 0 : sum;
    maxSum = Math.Max( currentSum, maxSum );
    }

    return maxSum;
    }