Revision: 8643
Updated Code
at October 9, 2008 02:58 by jaircazarin
Updated Code
/*
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;
}
Revision: 8642
Initial Code
Initial URL
Initial Description
Initial Title
Initial Tags
Initial Language
at October 1, 2008 15:58 by jaircazarin
Initial Code
/*
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;
}
Initial URL
Initial Description
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.
Initial Title
Maximum sub-array sum
Initial Tags
Initial Language
C