子阵最大总和

我找了，我完成了前几天，意识到我不应该使用常量的分配。该任务是众所周知的“使用分而治之的方法递归地发现正整数和负整数的子阵列的最大总和”问题。我的算法有效，但其中的一部分使用常量来计算包含数组中间的最大子数组总和。子阵最大总和

下面是相关代码：

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;

这样做是它遍历整个数组和检查各占一半，看是否总和大于最小的整数的情况下，较大的可能在整个阵列为负。如果是，它将该边的最大总和设置为总和值。如果该值大于递归调用的返回值（lfMax或rtMax），则将相应端的递归值设置为该值。

就像我刚才所说，这工作得很好，但我不应该使用“Integer.MIN_VALUE的”。有没有其他的方法呢？显然，我可以将lfSum/rtSum初始化为Integer.MIN_VALUE的数值，但我想知道是否还有其他选项。

我试着删除rtSum/lfSum，只是比较和递归值，以及初始化lfSum/rtSum为0，但都没有正常工作。感谢您抽时间阅读！

来源

2013-03-03 stevenelberger

你是什么意思“我不应该使用MIN_VALUE”？ – 2013-03-03 22:25:30

就像你指出，你可以只使用MIN_VALUE'的'的价值，我真的不看，你为什么“不能使用” – KodeSeeker 2013-03-03 22:27:58

奇怪的分配限制......但是，你总是可以采取的第一项之和要第一个值。 – 2013-03-03 22:36:47

可以初始化lfSum为null：

Integer lfSum = null;

并修改，如果条件是这样的：

if (lfSum == null || (lfSum != null && sum > lfSum.intValue())) { 
    lfSum = sum; 
    if (lfSum > lfMax) { 
     lfMax = lfSum; 
    } 
}

类似的策略应用于rtSum。

来源

2013-03-03 22:33:20

工作就像一个魅力。非常感谢你！ – stevenelberger 2013-03-03 23:08:37

子阵最大总和

回答

相关问题