Algorithm : 1D Maxsum (Kadane algorithm with resulted sequence size >= 1)

// Written by Kevin C. Wong
// @JEngineTeam 2/9/2012

// This function is designed to solve uva108 maximum sum problem with dynamically programming.
// You can extend this to solve the 2D array in O(n^3).

//    http://acm.uva.es/p/v1/108.html 

// The original Kadane algorithm will return empty sequence if all array values are negative.
// We just return a sequence with single min value.

#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;


int max1d(int a[], int n, int &x1, int &x2)
{
    int max=0;
    int umax=a[0],ui=-1;
    int here=0;
    int c=0;
    x1=x2=-1;
    rep(i,0,n-1)
    {
        if(a[i]>=umax){umax=a[i];ui=i;};
        c+=a[i];
        if(c<0){here=i+1;c=0;};
        if(c>max){max=c;x1=here;x2=i;};
    }
    if(x1==-1){x1=ui;x2=ui;return umax;}
    return max;
}