Find the sub-array of max sum http://basicalgos.blogspot.com/2012/05/52-find-sub-array-of-max-sum.html

max_subarray.c

#include <stdlib.h>
#include <stdio.h>

typedef struct solution {
	int start;
	int end;
	int sum;
} solution;

int sum_array(int *array, int count) {
	if (count == 0)
		return 0;

	int sum = 0;
	for (int i = 0; i < count; ++i)
	{
		sum += array[i];
	}

	return sum;
}

solution max_subarray (int *array, int count) {
	solution mySolution = {0, count-1, sum_array(array, count)};
	for (int i = 0; i < count; ++i) {
		for (int j = i; j < count; ++j) {
			int sum = sum_array(array+i, j-i+1);
			if (sum > mySolution.sum) {
				mySolution.start = i;
				mySolution.end = j;
				mySolution.sum = sum;
			}
		}
	}

	return mySolution;
}

int main(int argc, char *argv[]) {
	int count = argc - 1;

	int *input = malloc(count);

	for (int i = 0; i < count; ++i)
	{
		input[i] = atoi(argv[i+1]);
	}

	solution mySolution = max_subarray(input, count);

	printf("i = %d, j = %d, sum = %d\n", mySolution.start, mySolution.end, mySolution.sum);

	return 0;
}