面试题31：连续子数组的最大和。

题目：

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

解题思路

解题思路1(推荐)：

(1)设置两个变量，一个保存当前遍历的子数组的和，一个保存最大值的子数组和。接着遍历数组。

(2)当遍历到当前元素时，如果当前子数组和是小于等于0的，则将当前子数组和设置为当前元素，否则将当前元素加入到当前子数组和。

(3)如果当前子数组和大于最大子数组和，则将最大子数组和设置为当前子数组和。解题思路二（推荐使用）:用循环实现，利用前两项已经计算出来的结果，计算下一个，时间复杂度O(n)。

解题思路2:（使用动态规划，递归形式）

(1)当以第i-1个数字结尾的子数组中所有数字的和小于0时，如果把这个负数与第i个数累加，得到的结果比第i个数字本身还要小，所以这种情况下，以第i个数字结尾的子数组就是第i个数字本身。

(2)如果第i-1个数字结尾的子数组中所有数字的和大于0，则与第i个数字累加就得到以第i数字结尾的子数组中所有数字的和

(3)需要注意的是，每次返回前要先和最大子数组进行比较，如果大于最大子数组和，则将该值设置为最大子数组和