Skip to content

Instantly share code, notes, and snippets.

@nilsou
Created October 13, 2013 17:21
Show Gist options
  • Save nilsou/6964842 to your computer and use it in GitHub Desktop.
Save nilsou/6964842 to your computer and use it in GitHub Desktop.
#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;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment