[Google Interview] No. 03 - Maximum Sum of All Sub-arrays

Question: A sub-array has one number of some continuous numbers. Given an integer array with positive numbers and negative numbers, get the maximum sum of all sub-arrays. Time complexity should be O(n).

Solution with O(nxn):

listall.c

int main(int argc, char **argv)

{

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

    int listnum = sizeof(list)/sizeof(int);

    int k;

    printf("listnum=%d\n", listnum);

    for (k=0; k<listnum; k++)

    {

        printf("%d ", list[k]);

    }

    printf("\n");

    int i, j, sum=0, cursum=0;

    int start=0, end=0;

    for (i=0; i<listnum; i++)

    {

        cursum=list[i];

        if (cursum > sum)

        {

            start = i;

            end = i;

            sum = cursum;

        }

        for (j=(i+1); j<listnum; j++)

        {

            cursum+=list[j];

            if (cursum > sum)

            {

                start = i;

                end = j;

                sum = cursum;

            }

        }

    }

    printf ("maxsum=%d, start[%d]=%d, end[%d]=%d\n", sum, start, list[start], end, list[end]);

    return 0;

}


Solution with O(n):

int main(int argc, char **argv)
{
        //int list[]={1, -2, 3, -3, 10, -4, 8, 7, 2, -5, 2};
        //int list[]={1, -2, 3, 10, -4, 7, 2, -5};
        int list[]={-2, 1, -3, 4, -1, 2, 1, -5, 4};
        int listnum = sizeof(list)/sizeof(int);

        int k;
        printf("listnum=%d\n", listnum);
        for (k=0; k<listnum; k++)
        {
                printf("%d ", list[k]);
        }
        printf("\n");

        int i, j, sum=0, cursum=0;
        int start=0, end=0;
        for (i=0; i<listnum; i++)
        {
                cursum+=list[i];
                if (cursum <= 0)
                {
                        if ( (i+1) < listnum )
                        {
                                start = i+1;
                        }
                        cursum = list[i];
                }
                else
                {
                        cursum+=list[i];
                }

                if (cursum > sum)
                {
                        end = i;
                        sum = cursum;
                }
        }

        printf ("maxsum=%d, start[%d]=%d, end[%d]=%d\n", sum, start, list[start], end, list[end]);
        for (k=0; k<(end-start+1); k++)
        {
                printf("%d ", list[k+start]);
        }
        printf("\n");
        return 0;
}

Results:
listnum=9
-2 1 -3 4 -1 2 1 -5 4
maxsum=9, start[3]=4, end[6]=1
4 -1 2 1

Can also check Kadane's algorithm.

Ref: http://codercareer.blogspot.tw/2011/09/no-03-maximum-sum-of-all-sub-arrays.html