题目(数组中连续子数组的最大和)
输入一个整数数组，数组里有正数也有负数。数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为 O(n)。例如输入的数组为 {1,-2,3,10,-4,7,2,-5}，最大的连续子数组为 {3,10,-4,7,2}，因此输出为该子数组的和 18。
算法思路
本题是经典的动态规划题目之一,所以我们利用动态规划的思路分析。首先以函数 f(i) 表示以第 i 个数字结尾的子数组的最大和，那么求解目标就是max(f(i))，(0<=i<=n)。那么如果以第 i-1 个数字结尾的子数组的和小于等于 0，那么我们所求的子数组只能从第 i 个数字开始了;如果以第 i-1 个数字结尾的子数组的和大于 0，那么我们再将第 i 个数字累积进去，得到新的子数组的和，最后只需要和已有最大值比较即可。据此很容易得到状态转移方程为：
算法实现
参考
[1] <<剑指offer2>>
[2] 牛客网