patterncMinor
Largest contiguous sub-array sum
Viewed 0 times
contiguousarraysublargestsum
Problem
Challenge
Determine the largest contiguous sum of integers in a list.
Specifications
Sample Input
-10,2,3,-2,0,5,-15
2,3,-2,-1,10
Sample Output
8
12
Source
First time using
Determine the largest contiguous sum of integers in a list.
Specifications
- The first argument is a path to a file.
- The file contains multiple lines.
- Each line is a test case represented by a comma separated list of integers.
- For each test case, find and print the largest contiguous sub-array sum.
Sample Input
-10,2,3,-2,0,5,-15
2,3,-2,-1,10
Sample Output
8
12
Source
#include
#include
#define LINE_LENGTH 1024
#define MIN_INT -32768
int largest_contiguous_sum(int *array, int size) {
int max = MIN_INT;
int current_max = MIN_INT;
for (int i = 0; i array[i] ? current_max + array[i] : array[i];
max = max > current_max ? max : current_max;
}
return max;
}
int compute_largest_contiguous_sum(char *line) {
char seperator[] = ",";
char *token;
int var;
int array[512];
int i = 0;
token = strtok(line, seperator);
while (token != NULL) {
sscanf(token, "%d", &var);
array[i++] = var;
token = strtok(NULL, seperator);
}
return largest_contiguous_sum(array, i);
}
int main(int argc, char *args[]) {
if (argc 2) {
puts("Excessive arguments, only the first will be considered.");
}
FILE *file = fopen(args[1], "r");
if (file == NULL) {
perror("Error");
return 1;
}
char line[LINE_LENGTH];
while (fgets(line, LINE_LENGTH, file)) {
printf("%d\n", compute_largest_contiguous_sum(line));
}
fclose(file);
}First time using
strtok and wondering if there was a better tool.Solution
-
-
Notice that
-
MIN_INT looks pretty arbitrary (are you by any chance on a 16-bit system?). Better initialize max and current_max to array[0] (and start iterating from i = 1).-
current_max = current_max + array[i] > array[i] ? current_max + array[i] : array[i]; is extremely hard to read.Notice that
current_max + array[i] > array[i] is a long way to say current_max > 0.-
compute_largest_contiguous_sum does a bit more than its name suggests. It parses the input and computes the sum. I recommend to factor the parser out, e.g. int parse_input_line(char , int size);. As a side note, 512 is also quite arbitrary.Context
StackExchange Code Review Q#141757, answer score: 4
Revisions (0)
No revisions yet.