1、连续子数组的最大和

来源：剑指offer面试题31

题目，输入一个整形术组，数组里有整数也有负数，数组中一个或连续的多个整数组成一个子数组，求所有子数组的和的最大值，要求时间复杂度为O(n)

例子：int arr[] = {1,-2,3,10,-4,7,2,-5};
在遍历整个数组的过程中，我们可以发现数组中每一个数字为子数组尾部（假设长度为m），对应的子数组和，都是和前面m-1个数字的和有关系的，这就说明子问题之间是有重复计算的更小的子问题（子问题重叠）【重叠的子问题我们要申请数据结构或者用题目中原有的数据结构来保存以防止重复计算】，并且大问题的最优解也是由子问题的最优解组合而成的（最优自结构），所以我们可以很明显知道这可以用动态规划的思想来解。

分析此题可知，如果当前数字之前子数组的和为负数的话，那么之前的和加上当前数字的值反而变小了，如例子中1+(-2)=-1，那么如果3再加入此数组，和从3开始一个新的数组，和反而变小了（变为2），那么我们当然从3开始重新计算啦。这说明f(n-1)<=0的时候，我们是放弃之前的数组和的。否则我们会继续进行累加。可得公式如下：