对于一个数组a，我们需要找到其中连续的几个数使得它们的和最大。最容易想到的方法是尝试每一对起始索引与结束索引，得出它们的和。这样得到的时间复杂度为O(n^2)级别。下面我们设计一种更好的方式来计算，使得时间复杂度可以降为O(n*log n)。
工具/原料
1
jdk
2
idea
方法/步骤
1
我们首先描述这个问题的解决思路。基本的思路是采用分治法：对于一个数组A[low...high]，将其从中间分为两个部分a[low...mid]与a[mid+1...high]。这样，任何连续子数组必定属于以下三种情况之一：1.完全位于左侧数组；2.完全位于右侧数组；3.跨越了中间元素的数组。
2
我们可以在线性时间内求出跨越mid位置元素的子数组。从mid位置开始，依次向两侧搜索，可以获得跨越mid位置元素的子数组，返回最终的左侧位置、右侧位置与最大和。
3
然后使用递归找出长度缩小一半的两部分数组的最大子数组，最后返回三者之中的最大值，递归出口为数组只有一个元素。以下为该思路的伪代码。
4
下面我们使用java语言实现以上的算法。首先，由于以上两个函数返回值均为多个值，但数据类型均为整型，因此返回值为List
6
然后使用递归策略，反复调用该方法，每调用一个，数组的长度减半，直到每一个数组只剩下一个元素时，递归开始回溯。
7
接下来测试以上的算法，使用数组{13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7}，测试代码如下。这里使用流操作与Lambda表达式输出子数组。
8
输出结果如下，与实际的最大值相同。