给定一个无序矩阵，其中元素可正，可负，可0，求子矩阵的最大和
[原型]http://www.jianshu.com/writer#/notebooks/5320868/notes/5142304
思路：
- 首先暴力是可以解决的。复杂度为O(n6)。(确定左上点后，右下方点的数量级n2,可以作为左上角点的点的数量n2，所以子矩阵的数量O(n4)，然后需要求解每个子矩阵的和O(n2)，所以O(n6))
- 接下来讲解一个O(n^3)的解法，碉堡了。
算法步骤
- 两层for循环实现。res记录最大累加和。首先由第一行求出这个子数组的最大累加和，然后第二行加到第一行上，同理求解加上去之后的子数组最大累加和，这个过程知道最后一行。
- 然后不用管第一行了，从第二行开始，同理先求第二行，然后第三行加到第二行上，。。。，最后一行加到第二行上的最大累加和
- 然后第三方开始，第四行开始。。。直到最后一行开始。搞定
过程中注意更新全局最大res。
算法原理
第一行：3 2 1 4
第二行：6 5 -1 1
累加和：9 7 0 5
如上所示，假如我能求得行累加和数组的最大累加和，那么这个最大累加和就是必须包含两行的最大累加和
（你实际上是在选择列），那么回到这个问题，
假设原数组为：
3 2 1 4
6 5 -1 1
3 -3 -4 6
我们首先求1行； 1，2行累上；1 2 3行类上的最大累加和，2 行；2 3行累上的最大累加和3行最大累加和
这些子矩阵的累加和，那么最后求得的最大就是原矩阵的子数组的最大累加和。
（子数组行是不可分离的，任何一个子矩阵必然包含某几个连着的行，我们上面的解法把所有的情况都考虑到）
这样选行是O(n^2),选列为O(n)，搞定。
代码
public static int maxSum(int[][] arr){
if(arr==null||arr.length==0||arr[0].length==0)
return 0;
int res=Integer.MIN_VALUE;
int cur;
int[] h=null;
for(int i=0;i<arr.length;i++){
h=new int[arr[i].length];
for(int j=i;j<arr.length;j++){
cur=0;
for(int k=0;k<arr[j].length;k++){
h[k]+=arr[j][k];
cur+=h[k];
res=Math.max(cur,res);
cur=cur<0?0:cur;
}
}
}
return res;
}
