Find the contiguous subarray within an array (containing at least one number) which has the largest sum

Question

Interview Q: Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example: Given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

For this problem, return the maximum sum.

My solution (pseudocode and code) is below. Works, but can someone tell me

1. Is there a faster algo?

2. Is the code structure done for an interview?

Pseudocode

//maxTillNow=A[0]
//maxStart=0
//maxLength=1
//Set currIndex =0
//Loop till currIndex == arrayLength
//  Set offset,sum=0
//      If A(currIndex] is -ve, then the only thing you need to do is check if it is > maxTillNow (in case all elements are -ve). If yes, set maxTillNow to A[currIndex] and move on

//      if +ve
//          Look at sums of elements starting at A[currIndex] ... A[currIndex+offset] for offsets in range 0 to currIndex+offset<length
//            if any sum > maxTillNow, store
//            Also find index of first -ve element you encounter as you look at elements A[currIndex+1]... -->firstNegIndex
//            nextElement to look at it firstNegIndex+1

Full code

int maxSubArray(const int* A, int n1) {
    int currIndex=0;
    int maxSumTillNow=A[0] ;
    int maxSumStart=0 ;
    int maxSumLength=1 ;
    int currLength;
    int sum ;
    int firstNeg ;

    while(currIndex<=n1-1)
    {
        if(A[currIndex]<0)
        {
            if(A[currIndex]>maxSumTillNow)
                maxSumTillNow=A[currIndex] ;
            currIndex++ ;
            continue ;
        }
        sum=0 ;
        firstNeg=-1 ;
        for(currLength=0;currLength+currIndex<=n1-1;currLength++)
        {
            sum+=A[currIndex+currLength] ;
            if(sum>maxSumTillNow)
            {
                maxSumTillNow=sum ;
                maxSumStart=currIndex ;
                maxSumLength=currLength+1 ;
            }
            if(firstNeg==-1 && A[currIndex+currLength]<0)
            {
                firstNeg=currIndex+currLength ;
            }
        }
        if(firstNeg==-1)
        {
            break ;
        }
        currIndex=firstNeg+1 ;
    }
    return maxSumTillNow ;

   }

I can also get additional info on exact sequence leading to max sum as below

    //    printf("Max sum is = %d, starting at index %d and length =%d\n",maxSumTillNow,maxSumStart,maxSumLength) ;
    //    printf("Max sub Array is [") ;
    //    for(currIndex=maxSumStart;currIndex<=maxSumStart+maxSumLength-1;currIndex++)
    //    {
    //        printf("%d,",A[currIndex]) ;
    //    }
    //    printf("]\n") ;

      }

Answer 1

1

The usual C coding conventions dictate that a space is added before and after a binary operator. For example, you should write

a += b;
if (foo < bar) ...
int currIndex = 0;

instead of

a+=b;
if(foo<bar) ...
int currIndex=0;

Also, you should add a single space before the opening parenthesis associated with keywords for, while, and if. For example, you should write

for (i = 0; i < x; ++i) ...

instead of

for(i = 0; i < x; ++i) ...

2

You add a space (sometimes) before the closing semicolon (;). Don't do it.

3

Your code would be more nifty if you added an empty line after each closing brace (}). For example,

if (sum > maxSumTillNow)
{
    ...
}

if (firstNeg == -1 && A[currIndex + currLength] < 0)
{
    ...
}

4

Your algorithm seems to run in quadratic time. The Kadane's algorithm does this in linear time.

Summa summarum

All in all, I had this in mind:

#include <stdio.h>
#define MAX(a, b) (a) > (b) ? (a) : (b)

int maxSubArray(const int* A, int n1)
{
    int currIndex     = 0;
    int maxSumTillNow = A[0];
    int maxSumStart   = 0;
    int maxSumLength  = 1;
    int currLength;
    int sum;
    int firstNeg;

    while (currIndex <= n1 - 1)
    {
        if(A[currIndex] < 0)
        {
            if(A[currIndex] > maxSumTillNow)
            {
                maxSumTillNow = A[currIndex];
            }

            currIndex++;
            continue;
        }

        sum = 0;
        firstNeg = -1;

        for (currLength = 0; currLength + currIndex <= n1 - 1; currLength++)
        {
            sum += A[currIndex+currLength];

            if (sum > maxSumTillNow)
            {
                maxSumTillNow = sum;
                maxSumStart   = currIndex;
                maxSumLength  = currLength + 1;
            }

            if (firstNeg == -1 && A[currIndex + currLength] < 0)
            {
                firstNeg = currIndex+currLength;
            }
        }

        if(firstNeg == -1)
        {
            break ;
        }

        currIndex = firstNeg + 1;
    }

    return maxSumTillNow;
}

int kadanesAlgorithm(const int* array, const size_t length)
{
    int maximum_so_far = array[0];
    int maximum_end    = array[0];

    for (size_t index = 1; index < length; ++index)
    {
        const int x    = array[index];
        maximum_end    = MAX(maximum_end + x, x);
        maximum_so_far = MAX(maximum_end, maximum_so_far);
    }

    return maximum_so_far;
}

int main(int argc, const char * argv[]) {
    int arr[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4 };
    printf("Original result: %d\n", maxSubArray(arr, 9));
    printf("Kadane's result: %d\n", kadanesAlgorithm(arr, 9));
}

Hope that helps.