数组和矩阵问题：子数组的最大累加和问题

【题目】

　　给定一个数组 arr, 返回子数组的最大累加和。

　　例如， arr=[1, -2, 3, 5, -2, 6, -1]，所有的子数组中，[3, 5, -2, 6] 可以累加出的最大的和 12，所以要返回 12.

【要求】

　　如果 arr 的长度为 N，要求时间复杂度为 O(N), 额外空间复杂度为 O(1).

【难度】

　　一星

【解答】

　　如果 arr 中没有正数，产生的最大累积和一定是数组中的最大值。

　　如果 arr 中有正数，从左到右遍历 arr, 用变量 cur 记录每一步的累加和，遍历到正数 cur 增加，遍历到负数 cur 减少。当 cur < 0 时，说明累加到当前数出现了小于 0 的结果，那么累加的这一部分肯定不能作为产生最大累加和的子数组的左边部分，此时令 cur=0，表示从下个数开始累加。当 cur > 0 时，每一次累加都可能是最大的累加和，所以，用另外一个变量 max 全程跟踪记录 cur 出现的可能的最大值即可。

　　求解最大累加和的实现过程如下面代码中的 maxSum 方法

 1 public class Main {
 2     
 3     public static void main(String[] args) {
 4         int[] arr = {1, -2, 3, 5, -2, 6, -1};
 5         System.out.println(new Main().maxSum(arr));//12
 6     }
 7     
 8     public int maxSum(int[] arr){
 9         if(arr == null || arr.length == 0) return 0;
10         int cur = 0;
11         int max = Integer.MIN_VALUE;
12         for(int i = 0, len = arr.length; i < len; i++){
13             cur += arr[i]; 
14             max = Math.max(max, cur);
15             cur = cur < 0 ? 0 : cur;
16         }
17         return max;
18     }
19     
20 }