一、子数组的最大累加和问题
题目：
给定一个数组，返回子数组的最大累加和。
例如：arr=[1,-2,3,5,-2,6,-1]，所有子数组中，[3,5,-2,6]可以累加出最大的和12，return 12.
要求：
时间复杂度为O(N)，额外空间复杂度为O(1)。
思路：
如果arr中没有正数，产生的最大累加和一定是数组中的最大值。
如果arr中有正数，从左向右遍历arr，用变量cur记录每一步的累加和，遍历到正数cur增加，遍历到负数cur减少。当cur<0时，舍弃当前部分，令cur=0，表示重新从下一个数开始累加。当cur>=0时，每一次的累加都可能是最大的累加和，所以，用另外一个变量max全程跟踪cur出现的最大值。
public static int maxSum(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int cur = 0;
for (int i = 0; i != arr.length; i++) {
cur += arr[i];
max = Math.max(max, cur);
cur = cur < 0 ? 0 : cur;
}
return max;
}
二、子矩阵的最大累计和问题
题目：
给定一个矩阵，其中的值有正、有负、有0。返回子矩阵的最大累计和。
核心思路：
如果一个矩阵一共有K行且限定必须含有K行元素的情况下，只要把矩阵中每一行的K个元素累加生成一个累加数组，然后求出这个数组的最大累加和，这个最大累加和就是必须含有K行元素的子矩阵中的最大累加和。
public static int maxSum(int[][] m) {
if (m == null || m.length == 0 || m[0].length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int cur = 0;
int[] s = null;
for (int i = 0; i != m.length; i++) {
s = new int[m[0].length];
for (int j = i; j != m.length; j++) {
cur = 0;
for (int k = 0; k != s.length; k++) {
s[k] += m[j][k];
cur += s[k];
max = Math.max(max, cur);
cur = cur < 0 ? 0 : cur;
}
}
}
return max;
}