题目出自算法导论第三版，4.1-5.
线性算法的核心思想是如果已知A[1...j]的最大子数组，那么对于A[1...j+1]中的最大子数组：要么包括A[j+1]；要么不包括A[j+1],即就是原最大子数组。
该题中提出“在已知A[1...j]中最大子数组的情况下，可以在线性时间内找出形如A[i...j+1](1<=i<=j+1)的最大子数组”，这一点让我大惑不解。如果这样是线性的话，那遍历数组，总的解法不又是O(N²)了么？又何谈O(N)?
必然得在常量时间内找出A[i...j+1]才行。
那么如何在常量时间内找出它呢？
首先我们分析包括A[j+1]的最大子数组的起始元素A[i]。
整个数组可被一些临界元素分割为一系列正和连续子段。对于其中任一子段，设其首元素为A[k],尾元素为A[h],则对任意 m (k<m<=h) 均有 sum(A[k...m]) > 0. 但A[h+1] + sum(A[k...h]) <= 0.
A[i] 就是距离A[j+1]最近的正和子段的首元素。为什么呢？
具体证明见：
http://segmentfault.com/a/1190000000733277
找到了包括A[j+1]的最大子数组，然后比较A[1...j]的最大子数组与其的大小，重复如此至A[N], 即得出最大子数组。
参考：http://segmentfault.com/a/1190000000733277
http://www.xuebuyuan.com/1265810.html