Largest Sum Contiguous Subarray

Problem Statement:Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Data Structure Used:Array

O(N^3) Algorithm

#include
#include
#include

#define MAXN 10000000
int n;
float x[MAXN];

void sprinkle() /* Fill x[n] with reals uniform on [-1,1] */
{ int i;
for (i = 0; i < n; i++) x[i] = 1 - 2*( (float) rand()/RAND_MAX); } float alg1() { int i, j, k; float sum, maxsofar = 0; for (i = 0; i < n; i++) for (j = i; j < n; j++) { sum = 0; for (k = i; k <= j; k++) sum += x[k]; if (sum > maxsofar)
maxsofar = sum;
}
return maxsofar;
}

O(N^2) Algorithm

float alg2()
{ int i, j;
float sum, maxsofar = 0;
for (i = 0; i < n; i++) { sum = 0; for (j = i; j < n; j++) { sum += x[j]; if (sum > maxsofar)
maxsofar = sum;
}
}
return maxsofar;
}

float cumvec[MAXN+1];

float alg2b()
{ int i, j;
float *cumarr, sum, maxsofar = 0;
cumarr = cumvec+1; /* to access cumarr[-1] */
cumarr[-1] = 0;
for (i = 0; i < n; i++) cumarr[i] = cumarr[i-1] + x[i]; for (i = 0; i < n; i++) { for (j = i; j < n; j++) { sum = cumarr[j] - cumarr[i-1]; if (sum > maxsofar)
maxsofar = sum;
}
}
return maxsofar;
}

/* MS VC++ has a max macro, and therefore a perf bug */

#ifdef max
#undef max
#endif


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

float maxfun(float a, float b)
{ return a > b ? a : b;
}

#define max(a, b) maxfun(a, b)

float recmax(int l, int u)
{ int i, m;
float lmax, rmax, sum;
if (l > u) /* zero elements */
return 0;
if (l == u) /* one element */
return max(0, x[l]);
m = (l+u) / 2;
/* find max crossing to left */
lmax = sum = 0;
for (i = m; i >= l; i--) {
sum += x[i];
if (sum > lmax)
lmax = sum;
}
/* find max crossing to right */
rmax = sum = 0;
for (i = m+1; i <= u; i++) { sum += x[i]; if (sum > rmax)
rmax = sum;
}
return max(lmax + rmax,
max(recmax(l, m), recmax(m+1, u)));
}

float alg3()
{ return recmax(0, n-1);
}

O(N) Algorihtm

Kadane’s Algorithm:

Initialize:
max_so_far = 0
max_ending_here = 0

Loop for each element of the array
(a) max_ending_here = max_ending_here + a[i]
(b) if(max_ending_here < 0)
max_ending_here = 0
(c) if(max_so_far < max_ending_here)
max_so_far = max_ending_here
return max_so_far

Explanation:
Simple idea of the Kadane's algorithm is to look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far


float alg4()
{ int i;
float maxsofar = 0, maxendinghere = 0;
for (i = 0; i < n; i++) {
maxendinghere += x[i];
if (maxendinghere < 0)
maxendinghere = 0;
if (maxsofar < maxendinghere)
maxsofar = maxendinghere;
}
return maxsofar;
}

float alg4b()
{ int i;
float maxsofar = 0, maxendinghere = 0;
for (i = 0; i < n; i++) {
maxendinghere += x[i];
maxendinghere = maxmac(maxendinghere, 0);
maxsofar = maxmac(maxsofar, maxendinghere);
}
return maxsofar;
}

float alg4c()
{ int i;
float maxsofar = 0, maxendinghere = 0;
for (i = 0; i < n; i++) {
maxendinghere += x[i];
maxendinghere = maxfun(maxendinghere, 0);
maxsofar = maxfun(maxsofar, maxendinghere);
}
return maxsofar;
}

int main()
{ int algnum, start, clicks;
float thisans;

while (scanf("%d %d", &algnum, &n) != EOF) {
sprinkle();
start = clock();
thisans = -1;
switch (algnum) {
case 1: thisans = alg1(); break;
case 2: thisans = alg2(); break;
case 22: thisans = alg2b(); break;
case 3: thisans = alg3(); break;
case 4: thisans = alg4(); break;
case 42: thisans = alg4b(); break;
case 43: thisans = alg4c(); break;
default: break;
}
clicks = clock()-start;
printf("%d\t%d\t%f\t%d\t%f\n", algnum, n, thisans,
clicks, clicks / (float) CLOCKS_PER_SEC);
if (alg4() != thisans)
printf(" maxsum error: mismatch with alg4: %f\n", alg4());
}
return 0;
}

To print the sub array run here 
Time Complexity O(n)
Space Complexity O(1)
http://ideone.com/9yyf6J

Source Jon Bently Programming Pearls