Largest contiguous sub-array sum

Question

Challenge

Determine the largest contiguous sum of integers in a list.

Specifications

1. The first argument is a path to a file.
2. The file contains multiple lines.
3. Each line is a test case represented by a comma separated list of integers.
4. 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 <stdio.h>
#include <string.h>
#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 < size; i++) {
 current_max = current_max + array[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) {
 fprintf(stderr, "File path not provided. Exiting...\n");
 return 1;
 }
 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.

• Myridium: It looks to me as though largest_contiguous_sum just finds the largest contiguous sum which includes the first item in array. Have you tested the output of your program for a few sample inputs? Also, there is a std::max function in <algorithm> so you don't need to use those if statements to see which value is larger.
• Legato: Hey there. Look at the line including the update tocurrent max. Its value is updated to the value at a specific point if that specific point is higher, e.g. -3,1,-2,4,1 would effectively 'start' at 4. As for test cases, this passes all the ones one the cited challenge site.
• Myridium: In that case, does it return 28 from 5,5,5,-1,-1,5,5,5?
• Legato: Yes.

Answer 1

• 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.

• Legato: Yeah...buffer sizes. I never know how much to allocate, I just increase by powers of 2. It failed a few test cases before and passed with this. Min int is the lowest value a plain int could have, I thought. But good point about just starting wth the first element.
• vnp: @Legato Starting with the first element is a standard practice. Re buffer size - you know it never exceeds the length of input. If you have reasons to believe that the input length is going to be outrageously large, try two passes (first being a dry run to determine the buffer size).

Answer 2

For an input of all negative numbers, this implementation returns the highest negative number. I think that's wrong. In such test case the maximum value is the sum of the empty subsequence, which is 0.

This implies that you don't need to set an arbitrary MIN_INT value, the minimum value is 0.

Note that "current max" is a bit of a misnomer. "Current sum" would be more accurate and a bit more clear.

The ternary operators don't buy you much in this example. The logic will be clearer if you rewrite those with if statements. Note that when current sum dips below zero, you can reset it to 0, as the maximum sequence until this point is not going to contribute to the solution. And you only need to update the max when the current sum is above zero. Based on these considerations, the rewritten version using if statements will be quite clear.

Answer 3

Simplification + Bug

This part of your main computation expression strikes me as odd:

current_max + array[i] > array[i] ? ...

If you subtract array[i] from both sides of the comparison, you get the simpler:

current_max > 0 ? ...

So I started to think, is there any difference between the two expressions? There is, and that is where you have a potential bug. The addition of current_max + array[i] could overflow past the minimum integer, leading to an incorrect positive result. For example, if you ran your program on a machine with 16-bit integers, and the first item in your list were -1, your program would report 32767 as the max sum.

Sum too large

Another minor bug is that the maximum subarray sum may exceed the size of an integer. It's unclear from the problem desciption what you are supposed to do if that happens. One possibility would be to use a larger sized variable than an int to track the sum, and then return that larger sized variable. Another possibility would be to return the maximum integer value.