求一串数组的最大的子数组的和
此题目最笨的方法就是，多用几个循环嵌套，依次求出子数组中数组个数为1到n的各个数组的和，然后比较找出其最大值，思路固然简单，但是从执行效率上来看，往往不是最好的。下面介绍一种相对上面的方法来说，优化一点的算法，只需遍历一遍。
下面就以5个数的数组为例（5，-3，0，1，-2），下面就写出他们各个字数组的和的情况，为了便于以后的分析，就以倒三角的方式写出：
5 -3 0 1 -2
2 -3 1 -1
2 -2 -1
3 -4
1
由此可以看出数组中各个子数组的和的相对位置，其实可以看出他们和的位置都是很有规律的，假如把上面三角的各个数据用一个一维数组存储的话，一共需要n(n+1)/2个空间。下面就画出位置的相对情况（为了看着方便，就从1开始）：
1 2 3 4 5
6 7 8 9
10 11 12
13 14
15
下面的三角与上面的三角，位置与元素是一一对应的，由此如果只循环依次的话，就可以利用位置找元素。1与2号的位置上的元素和在6号位置，1,2,3号位置元素的和在10号位置，所以求后面的的和可以，运用前面的求过的和结果。既然思路清楚了，接下来就是如何实现的问题。
如果数组是5个数，那么最上层的就是五个数，第二层与第一层相差5，以后每次相差的数减1。这样的话就可以用计数的方法实现。用m记录当前层数，n记录当前层是否到头，然后利用当前的数组序列号与当前层的序号m,进行加法操作，然后再将和放入相应的位置，例如6号与7号位上的2与-3相加，但是要减去2号位置上的-3，结果是2放入放入10号位，这时的10号位是6加上此时的m值4。但是其中的集体的循环控制的细节如，如何判断结束，以及如何判断层的结束，以及每一层结束后，如何跳转，就不是问题的主要部分，就不写了。
原文：http://www.cnblogs.com/momo-jiji/p/3611068.html