/*
	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 Algorithm
int 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 algorithm
int 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;
}

/*
	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 Algorithm
int maxSubArray1(int array[], int size)
{
	int maxsofar = 0;
	for(int i = 0; i < size; i++)
	{
		int max = 0;
		for(int j = i+1; j < size; j++)
		{
			max += array[j];
			maxsofar = MAX(maxsofar, max);
		}
	}
	return maxsofar;
}

//Linear algorithm
int 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;
}

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.

Maximum sub-array sum

C