java - 从包含最大和的整数数组中提取子数组的算法

Question

有一个整数数组(包括正数和负数)。请建议一个算法，该算法将为您提供具有最大总和的子数组。示例:

int a[] = new int[]{2,3,-1,4,5,7,8,13,-20};

那么答案应该是 {4,5,7,8,13} 作为 4 + 5 + 7 + 8 + 13 = 37。

我无法为这个问题设计算法。

Answer 1

下面是这个问题的线性解:

long getMaximumSubarraySum(int[] a) {
    int start = 0; 
    int end = 0;
    long result = 0; // I assume that an empty subarray is allowed.
    long minPrefixSum = 0;
    int minPrefixSumPos = -1;
    long currentPrefixSum = 0;
    for (int i = 0; i < a.length; i++) {
        currentPrefixSum += a[i];
        if (currentPrefixSum - minPrefixSum > result) {
             result = currentPrefixSum - minPrefixSum;
             start = minPrefixSumPos + 1;
             end = i + 1;
        }
        if (currentPrefixSum < minPrefixSum) {
             minPrefixSum = currentPrefixSum;
             minPrefixSumPos = i;
        }
    }
    // The resulting subarray is [start; end).
    return result;
}

这个算法背后的想法非常简单:让我们看一下前缀和。那么答案就是max(prefixSum[i] - prefixSum[j])的最大值, 其中j < i对于所有 i .这正是这段代码所做的:它遍历输入数组，维护当前前缀总和和最小前缀总和，并选择最佳答案。