Return to Revisions

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.