有一个整数数组(包括正数和负数)。请建议一个算法,该算法将为您提供具有最大总和的子数组。 示例:
int a[] = new int[]{2,3,-1,4,5,7,8,13,-20};
那么答案应该是 {4,5,7,8,13}
作为 4 + 5 + 7 + 8 + 13 = 37
。
我无法为这个问题设计算法。
最佳答案
下面是这个问题的线性解:
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
.这正是这段代码所做的:它遍历输入数组,维护当前前缀总和和最小前缀总和,并选择最佳答案。
关于java - 从包含最大和的整数数组中提取子数组的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/28084436/