## Posted By

jaircazarin on 10/01/08

## Who likes this?

2 people have marked this snippet as a favorite

# Maximum sub-array sum

/ Published in: C

Given an array of integers, find the sub-array with maximum sum.

Interesting test cases:

• Empty array.
• One positive element.
• One negative element.
• Two or more elements.
• All negative.
• All positive.

`/*	Given an array of integers, find the sub-array with maximum sum.*/#include<stdio.h>#include<assert.h>#define MAX(a,b) ((a) < (b) ? (b) : (a)) //Quadratic Algorithmint maxSubArray1(int array[], int size){	int maxsofar = 0;	for(int i = 0; i < size; i++)	{		int max = 0;		for(int j = i; j < size; j++)		{			max += array[j];			maxsofar = MAX(maxsofar, max);		}	}	return maxsofar;} //Linear algorithmint maxSubArray2(int array[], int size){	int maxsofar = 0;	int currentmax = 0;	for(int i = 0; i < size; i++)	{		currentmax = MAX(currentmax + array[i], 0);		maxsofar = MAX(maxsofar, currentmax);	}	return maxsofar;} int main(){	int array[] = {-1, 2, 4, 28, -30, 50, 60, 80};	printf("%d", maxSubArray1(array, 8));	return 0;}`