Return the sub-array of the maximum sum

Question

In the book "elements of programming interviews", I came across, the problem of returning the subarray of the maximum sum. I tried their solution and I don't think we need to keep track of the minimum sum to get the array of the maximum sum:

I wrote another version of it maximumSumMine where I removed the minSum and it worked fine, the output in the comments

What is the purpose of tracking minSum, do we really need it?

#include <stdio.h>
#include <limits.h>

typedef struct range {
    int start;
    int end;
    int maxSum;
} range;

void print(int *a, int start, int end) {
    for (int i = start; i <= end; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
}

// Book's code as it is
range maximumSum(int *a, int n) {
    range r;
    r.start = 0; r.end = 0;
    int minSum = 0, sum = 0, minIndex = -1, maxSum = INT_MIN;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (sum < minSum) {
            minSum = sum;
            minIndex  = i;
        }
        if (sum - minSum > maxSum) {
            maxSum = sum - minSum;
            r.start = minIndex + 1;
            r.end = i + 1;
        }
    }
    return r;
}

range maximumSumMine(int *a, int n) {
    range r;
    r.start = 0; r.end = 0;
    int sum = 0, minIndex = -1, maxSum = INT_MIN;
    for (int i = 0; i < n; i++) {
        sum += a[i];
        if (sum < 0) {
            sum = 0;
            minIndex = i + 1;
        }
        if (sum > maxSum) {
            maxSum = sum;
            r.start = minIndex;
            r.end = i;
        }
    }
    return r;
}

void unitTests() {
    // Example 1
    int a[5] = {-2, 5, 1, -1, 4};
    range r = maximumSum(a, 5);
    print(a, r.start, r.end); // output 5 1 -1 4 0

    // Example 2
    int b[5] = {2, -5, 5, -1, 3};
    r = maximumSum(b, 5);
    print(b, r.start, r.end); // 5 -1 3 1

    // Example 1
    r = maximumSumMine(a, 5);
    print(a, r.start, r.end); // output 5 1 -1 4

    // Example 2
    r = maximumSum(b, 5);
    print(b, r.start, r.end); // 5 -1 3 1

}
int main() {
    unitTests();
    return 0;
}

You must have forgot to ask a question? You have only supplied an opinion, and a wall of code. — austin wernli
– austin wernli, Commented Feb 18, 2015 at 20:48
updated with a question @austinwernli Idon't understand why the author is using minSum — test
– test, Commented Feb 18, 2015 at 21:01
Nothing, it just took me a minute to remove my vote. Sorry about that — austin wernli
– austin wernli, Commented Feb 18, 2015 at 21:48

IVlad · Accepted Answer · 2015-02-18 21:16:26Z

4

You need the minimum sum because the algorithm involves computing prefix sums:

sums[i] = a[0] + a[1] + ... + a[i]

So for each i, the maximum sum you can get that ends at a[i] is sums[i] - min(sums[j < i]).

The book code implements this without actually using an array, as you can simply keep track of the minimum and the current prefix sum.

If you only take the max of the prefix sums under the conditions that you do, it will not work for negative maximum sums: you will always output 0 if the maximum sum is negative, because you will set your prefix sum to 0 when it becomes negative.

Sometimes, ignoring negative maximum sums can be perfectly fine, other times not. I've seen both versions given as programming assignments / questions.

Example:

a = {-1, -2, -3}
book output = -1
your output = 0

edited Feb 18, 2015 at 21:16

answered Feb 18, 2015 at 21:10

IVlad

43.6k13 gold badges115 silver badges184 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Return the sub-array of the maximum sum

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related