HiveBrain v1.2.0
Get Started
← Back to all entries
patterncMinor

Largest contiguous sub-array sum

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
contiguousarraysublargestsum

Problem

Challenge

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

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