Maximum Segment Sum in C

Given a list of numbers, the task is to compute the largest possible sum of a consecutive segment.


#include <stdio.h>
#include <stdlib.h>

#define max(a,b)  ((a) > (b) ? (a) : (b))

/* Order of algorithm O(n^2) */
int maxsegsumO2(int a[], int sz)
{
    int maxtillnow = 0, maxsofar = 0;
    int i,j;

    for (i = 0; i < sz; i++)
    {
        maxtillnow = 0;
        for (j = i ; j < sz; j++)
        {
           maxtillnow = max(0,a[j]+maxtillnow);
           maxsofar = max(maxtillnow,maxsofar);
        }
        printf("%5d, %5d\n", maxtillnow, maxsofar);

    }
    return maxsofar;
}

/* Order of algorithm O(n) */
int maxsegsumO1(int a[], int sz)
{
    int maxtillnow = a[0],  maxsofar = a[0];
    int i, begin, end, begin_tmp;

    for (i = 1; i < sz; i++)
    {
        if (maxtillnow < 0)
        {
           begin_tmp = i;
           maxtillnow = a[i];
        }
        else
           maxtillnow += a[i];

        if (maxtillnow >= maxsofar)
        {
           maxsofar = maxtillnow;
           begin = begin_tmp;
           end = i;
        }
        /*
        maxtillnow = max(0,a[i]+maxtillnow);
        printf("%5d, %5d\n", maxtillnow, maxsofar);
        maxsofar = max(maxtillnow,maxsofar);
        */
    }

    printf("%d, %d\n", begin, end);
    return maxsofar;
}

int main()
{
   //int A[] = {3, 4, 5, -40, -20, 21, 25, 29, 31, 35};
 //  int A[] = {2, -3, 4, -1, 3};
   int A[] = {-2, -3, 4, -1, -2, 1, 5, -3};

   printf ("max seg sum: %d\n", maxsegsumO2(A, sizeof(A)/sizeof(int)));
   printf ("max seg sum: %d\n", maxsegsumO1(A, sizeof(A)/sizeof(int)));

   return 0;
}