这个问题是一个经典的动态规划问题。思路简述如下：

对于某个中间状态S(i)，设元素a[i]之前的数组累加和为sum，a[i+1]...a[n]中与a[i]邻接的和最大的数组为amax，a[i+2]...a[n]中的最大数组为rmax。这里有三种情况。

1. a[i] >= 0. 因为a[i]与amax相邻，故和最大数组应为MAX(sum+a[i]+amax, rmax).

2. a[i] < 0 且 |a[i]| < sum，此时，a[i] + sum >0，显然sum+a[i]+amax构成一个比amax更大的数组，因此最大数组仍应为MAX(sum+a[i]+amax, rmax).

3. a[i] < 0 且 |a[i]| >= sum，此时sum+a[i]+amax构成的数组不会比amax更大，因此可以放弃a[i]，最大数组应为MAX(amax, rmax).

于是问题转化为下一状态S(i+1)，情况1, 2下sum = sum + a[i]，情况3 可将sum=0。 

对于a[0], sum=0, 整个计算过程sum始终为非负。