arrays - 返回最大和的子数组

Question

在《编程面试要素》一书中，我遇到了返回最大和的子数组的问题。我尝试了他们的解决方案，我认为我们不需要跟踪最小总和来获取最大总和的数组:

我写了另一个版本的 maximumSumMine，我删除了 minSum，它工作正常，评论中的输出

跟踪minSum的目的是什么，我们真的需要它吗？

#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;
}

Answer 1

您需要最小和，因为该算法涉及计算前缀和:

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

所以对于每个 i ，您可以获得的最大金额以 a[i] 结尾是sums[i] - min(sums[j < i]) .

书中的代码实现了这一点，实际上并没有使用数组，因为您可以简单地跟踪最小值和当前前缀和。

如果你在你做的条件下只取前缀和的最大值，它对负的最大和不起作用:如果最大和为负，你将始终输出 0，因为你会将你的前缀和设置为 0当它变为负数时。

有时，忽略负的最大总和可能完全没问题，有时则不然。我已经看到这两个版本都作为编程作业/问题给出。

例子:

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