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.

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.

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.