我正在查看几天前完成的一项作业,并意识到我不应该使用常量。该赋值是众所周知的“使用分而治之的方法递归地找到正负整数子数组的最大和”问题。我的算法有效,但其中一部分使用常量来计算出包含数组中间的子数组的最大总和。
相关代码如下:
lfSum = Integer.MIN_VALUE;
sum = 0;
// Sum from left to mid
for (int i = mid; i >= LF; i--) {
sum += array[i];
if (sum > lfSum) {
lfSum = sum;
if (lfSum > lfMax) {
lfMax = lfSum;
}
}
}
rtSum = Integer.MIN_VALUE;
sum = 0;
// Sum from mid to right
for (int j = mid+1; j <= RT; j++) {
sum += array[j];
if (sum > rtSum) {
rtSum = sum;
if (rtSum > rtMax) {
rtMax = rtSum;
}
}
}
// Largest sum spanning whole array
midMax = lfSum + rtSum; // midMax = leftMid + midRight;
它的作用是循环遍历整个数组的每一半,并检查总和是否大于可能的最小整数,以防整个数组为负数。如果是,则将该方的最大和设置为 sum 的值。如果该值大于递归调用返回的值(lfMax 或 rtMax),请将相应一侧的递归值设置为其。
就像我之前说的,这工作得很好,但我不应该使用“Integer.MIN_VALUE”。还有其他办法解决这个问题吗?显然我可以将 lfSum/rtSum 初始化为 Integer.MIN_VALUE 的数值,但我想知道是否还有其他选项。
我尝试删除 rtSum/lfSum 并将 sum 与递归值进行比较,并将 lfSum/rtSum 初始化为 0,但两者都无法正常工作。感谢您花时间阅读本文!
最佳答案
您可以将lfSum
初始化为null
:
Integer lfSum = null;
并修改 if 条件如下:
if (lfSum == null || (lfSum != null && sum > lfSum.intValue())) {
lfSum = sum;
if (lfSum > lfMax) {
lfMax = lfSum;
}
}
类似的策略适用于rtSum
。
关于java - 子数组最大和,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15191642/