(Maximum subarray prob) 找到最大子数组后，怎么还有n-1个选择2个子数组留给考虑？
(Maximum subarray prob) After finding the maximum subarray,how there is still n-1 choose 2 subarrays are left to consider?
我正在阅读 clrs 的算法导论第 3 版，第 69 页（最大子数组问题）中的段落..."A transformation"指出 n-1 选择 2 = Theta (n ^2) 仍然需要子数组 check.I 不明白，既然我们已经找到了最大子数组，那么为什么我们还需要进一步检查子数组……为什么从 n-1 中选择 2？我们正在选择子序列...不是两天...！
我查了一下书，发现可能你没有真正理解问题的重点，这道题可以转化为著名的子数组问题。
子数组问题给定一个数组，求其所有元素和最大的子数组
所以，书上的暴力算法的意思是，你可以检查子数组的所有起点和终点，也就是n-1选2，因为我们的数组有n-1个元素，并且我们可以选择两个中的任何一个作为开始和结束，
所以复杂度是O(n^2)，希望对你有帮助！
参考：算法导论第三版
我正在阅读 clrs 的算法导论第 3 版，第 69 页（最大子数组问题）中的段落..."A transformation"指出 n-1 选择 2 = Theta (n ^2) 仍然需要子数组 check.I 不明白，既然我们已经找到了最大子数组，那么为什么我们还需要进一步检查子数组……为什么从 n-1 中选择 2？我们正在选择子序列...不是两天...！
我查了一下书，发现可能你没有真正理解问题的重点，这道题可以转化为著名的子数组问题。
子数组问题给定一个数组，求其所有元素和最大的子数组
所以，书上的暴力算法的意思是，你可以检查子数组的所有起点和终点，也就是n-1选2，因为我们的数组有n-1个元素，并且我们可以选择两个中的任何一个作为开始和结束， 所以复杂度是O(n^2)，希望对你有帮助！
参考：算法导论第三版