Sub-Array with the Largest Sum

Question: You are given an array with integers (both positive and negative) in any random order. Find the sub-array with the largest sum.

Answer: This is an all-time favorite software interview question. The best way to solve this puzzle is to use Kadane’s algorithm which runs in O(n) time. The idea is to keep scanning through the array and calculating the maximum sub-array that ends at every position. The sub-array will either contain a range of numbers if the array has intermixed positive and negative values, or it will contain the least negative value if the array has only negative values. Here’s some code to illustrate.

void maxSumSubArray( int *array, int len, int *start, int *end, int *maxSum )
{
    int maxSumSoFar = -2147483648;
    int curSum = 0;
    int a = b = s = i = 0;
    for( i = 0; i < len; i++ ) {
        curSum += array[i];
        if ( curSum > maxSumSoFar ) {
            maxSumSoFar = curSum;
            a = s;
            b = i;
        }
        if( curSum < 0 ) {
            curSum = 0;
            s = i + 1;
        }
    }
    *start = a;
    *end = b;
    *maxSum = maxSumSoFar;
}

Think you have a better solution? We'd love to read your comments!

Continue Reading Below
If you're looking for some serious preparation for your interviews, I'd recommend this book written by a lead Google interviewer. It has 189 programming questions and solutions:

Book Cover
Button

25 Responses

  1. Amit Veerani says:

    //Updated solution
    public static int findMaxSubArray(int[] array)
    {
    int max=0,cumulativeSum=0,i=0,start=0,end=0,savepoint=0;
    while(i<array.length)
    {
    if(cumulativeSum+array[i]max)
    {
    max=cumulativeSum;
    savepoint=start;
    end=i;
    }
    i++;
    }

  2. Amit Veerani says:

    //There was some mistake in my previous //solution. Find Updated One

    public static int findMaxSubArray(int[] array)
    {
    int max=0,cumulativeSum=0,i=0,start=0,end=0,savepoint=0;
    while(i<array.length)
    {
    if(cumulativeSum+array[i]max)
    {
    max=cumulativeSum;
    savepoint=start;
    end=i;
    }
    i++;
    }

    System.out.println(“Max : “+max+” Start indices : “+savepoint+” end indices : “+end);
    return max;

    }

  3. Amit Veerani says:

    //Time complexity O(n)
    //space complexity : Zero
    public static void main(String… args)
    {
    int[] array={1,2,3,4,-9,6,7,-8,1,9};

    System.out.println(findMaxSubArray(array));

    }

    public static int findMaxSubArray(int[] array)
    {
    int max=0,cumulativeSum=0,i=0,start=0,end=0,savepoint=0;
    while(i<array.length)
    {
    if(cumulativeSum+array[i]max)
    {
    max=cumulativeSum;
    savepoint=start;
    end=i;
    }
    i++;
    }

    System.out.println(“Max : “+max+” Start indices : “+savepoint+” end indices : “+end);
    return max;

    }

  4. VISHWANATH says:

    This algorithm fails with the following values
    int arr[]={2,4,-5,6,8,12,-5,3,-4,49,45,-11,2,99};

    here largest sub array is {2,99}
    but the output shows only {99}

  5. Pramod says:


    public class Test {

    static int A[]={8,-8,9,-9,10,-11,12};

    public static int maxConsecutiveSum(int A[], int N){
    int start = 0;
    int end = N;
    int sum = 0;
    int maxSum = 0;
    int maxSumIndex = 0;
    int i=start;
    while(i != end) {
    sum = sum + A[i];
    if(sum > maxSum ) {
    maxSum = sum;
    maxSumIndex = start;
    }
    if (sum < 0) {
    end = start -1;
    if (end < 0) end = end + N - 1;
    start = i+1;
    i = start;
    sum = 0;
    continue;
    }
    i++; if (i == N) i=0;
    }
    System.out.println("max sum is =" + maxSum + "start element is" + maxSumIndex);
    return maxSum;
    }

    /**
    * @param args
    */
    public static void main(String[] args) {
    maxConsecutiveSum(A,7);
    }

    }

  6. Why not just iterate through the entire array, add only its positive members to the sub-array and maintain a cum of the members added.

  7. laxatives says:

    Also, I don’t understand the curSum < 0 check. This check always gets thrown if the entire input array contains negative values. Even if curSum decreases in value, that doesn't mean it isn't beneficial to maintain the start index. the array {1000, -1, 1000} is a simple counterexample

  8. laxatives says:

    I dont understand why you pass arguments start and end and return void. Redefining start and end within the method doesn’t change them outside the method’s environment since they’re both integers. Also, MaxSum is never initialized in the code

  9. Dinesh says:

    Here is my answer:
    Step1: Sort the array in ascending order.
    Step2: Calculate the sum of all positive numbers and calculate the sum of all negative numbers.
    Step3: Compare the values of these 2 (-ve and +ve) to decide the largest…

  10. snikons says:

    Here’s some code that works for these tests


    bool findMaxSubArray(const int *arr, const int arraySize, int *start, int *end, int *sum) {
    if(arraySize <= 0)
    return false;

    // Intitialize
    *start = 0;
    *end = 0;
    *sum = arr[0];

    int tempSum = *sum;
    int tempStart = *start;
    int tempEnd = *end;
    bool startNewRange = false;
    bool addToCurrentRange = false;

    for(int i = 1; i < arraySize; i++) {

    // case 1: adding current element increases tempSum
    // case 1a: tempSum = 0
    // addToCurrentRange = true;
    // case 2: adding current element decreases tempSum
    // startNewRange = true;
    // case 3: adding current element keeps tempSum unchanged
    // case 3a: tempSum = 0
    // addToCurrentRange = true;

    // case 1
    if(tempSum + arr[i] > tempSum) {
    if(tempSum < 0) { // case 1a
    startNewRange = true;
    } else { // case 1b
    addToCurrentRange = true;
    }
    }

    // case 2
    if(tempSum + arr[i] < tempSum) {
    startNewRange = true;
    }

    // case 3
    if(tempSum + arr[i] == tempSum) {
    if(tempSum = *sum) {
    // we found a higher sum
    // save it
    *sum = tempSum;
    *start = tempStart;
    *end = tempEnd;
    }
    }

    return true;
    }

  11. snikons says:

    Has a bug. Here are some results

    4, -2, 7, 4, -8, -6, 2, 9, 1, 0, -4
    start: 0 end: 3 sum: 13
    FAILED

    -4, -2, -7, -4, -8, -6, -2, -9, -1, -3, -4
    start: 8 end: 8 sum: -1
    PASSED

    -4, -2, -7, -4, -8, 0, -2, -9, -1, -3, -4
    start: 5 end: 5 sum: 0
    PASSED

    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11
    start: 0 end: 10 sum: 66
    PASSED

    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
    start: 0 end: 0 sum: 0
    PASSED

  12. Anonymous says:

    Taking care of special case when all the numbers are negative..

    int arrayMax = Integer.MIN_VALUE;
    int arrayMaxIndex = -1;
    for(int i = 0; i arrayMax)
    {
    arrayMax = arr[i];
    arrayMaxIndex = i;
    }
    }

    for(int i = 0; i maxSum)
    {
    e = i;
    maxSum = curSum;
    }

    if (curSum < arrayMax) {
    // curSum has reduced, so start again
    curSum = 0;
    s = i + 1;
    }
    }

    if (maxSum == arrayMax)
    {
    // s changes always in this case, make it equal to e
    s = e;
    }

  13. purushothgct says:

    #include
    int main()
    {
    int a[10]={2,5,-4,9,4,-14,-9,7,12,-13};
    int i,sum1=0,s2=0,max=0;
    for(i=0;i0)

    sum1=sum1+a[i];
    else
    {
    s2=sum1;
    sum1=0;
    }
    if(s2>sum1) max=s2;
    else max=sum1;
    }
    printf(“%d”,max);
    return ;
    }

  14. Krishna says:

    I think the original solution fails for this series 1,2,3,4,5,-1,7,8,9,10

    Did someone verify this ?

  15. srinidhi says:

    scan the elements one by one untill u encounter a negative value…once u get a -ve value add all the previous elements store it in some location…perform this by neglecting th negative values repeatedly…..then sort the sum values…represent the biggest sum …

  16. Deepa says:

    I have written a small function to get the max sum of the sub array in a given array . Please let me know if it fails at any case.
    public static void maxSumSubArray(int[] arr){
    int maxSum=arr[0];
    int sumTillPos=arr[0];
    for (int i = 1; i maxSum){
    maxSum=sumTillPos;
    }
    if(arr[i]>maxSum){
    maxSum=arr[i];
    sumTillPos=arr[i];
    }
    }
    System.out.println(“max sum sub array ::”+maxSum);
    }

  17. Mehdi says:

    what about doing a Merge sort (nlogn) or any other sort that is O(nlogn), and then test if the max value is =< 0 we just take that first element, if not we will be iterating until we get the first element that is =< 0 and we do not include it in the sub array.

  18. Doggie says:

    Yes Deepak, that would be O(n^2) which is not very ideal. The solution given is only O(n).

  19. Deepak says:

    Loop over the main array and create a new array which stores the sum of numbers in array
    Eg.
    sum_array[1] = array[1] + array[2]
    sum_array[2] = array[1] + array[2]+array[2]
    and so on..
    Once we the sum_array find out the maximum of sum_array.
    And repeat the same from array[2] to last

    May be this algorithm takes O(n^2).

  20. mhassan83 says:

    public static Integer[] subArrayWithLargestSum(Integer[] array) {
    List intList = new ArrayList();

    if (array.length > 0) {
    // first check to see if we get all positive number sub-array
    for (Integer i: array) {
    if (i > 0) intList.add(i);
    }

    // check to see if it has any ZERO number
    if (intList.size() == 0) {
    for (Integer i: array) {
    if (i == 0) {
    intList.add(0);
    break;
    }
    }
    }

    // means all are negative values
    if (intList.size() == 0) {
    Integer max = array[0];
    for (Integer i: array) {
    if (i >= max) {
    intList.remove(max);
    intList.add(i);
    max = i;
    }
    }
    }

    }

    return intList.toArray(new Integer[0]);
    }

  21. M says:

    Good site 🙂

  22. Purav says:

    would this code work?

    n = a.length;
    maxSum[n – 1] = a[n – 1]; //stores max possible sum starting from position i
    endPos[n – 1] = n – 1; //stores the length of max possible sum starting from i, ending at endPos[i] (inclusive)

    for(int i = n – 2; i >= 0; i–)
    {
    int x = a[i] + maxSum[i + 1];
    if(x >= a)
    {
    maxSum[i] = x;
    endPos[i] = end[i + 1];
    }
    else
    {
    maxSum[i] = a[i];
    endPos[i] = i;
    }
    }

  23. Aswin says:

    Yes we are looking for a contiguous sub-array in this case. If not, instead of sorting, you could just add all the positive integers in the array.

  24. Aidan says:

    Actually sorting wont work if you have to have a contigious sub-array.

  25. Aidan says:

    Could you sort the array and then work from the tail end backwards until you hit < 0?

Leave a Reply

Using Gravatars in the comments - get your own and be recognized!

XHTML: These are some of the tags you can use: <a href=""> <b> <blockquote> <code> <em> <i> <strike> <strong>