给定一个无序矩阵，其中元素可正，可负，可0，求子矩阵的最大和

[原型]http://www.jianshu.com/writer#/notebooks/5320868/notes/5142304

思路：

1. 首先暴力是可以解决的。复杂度为O(n^{6)。(确定左上点后，右下方点的数量级n}2,可以作为左上角点的点的数量n^{2，所以子矩阵的数量O(n}4)，然后需要求解每个子矩阵的和O(n^{2)，所以O(n}6))
2. 接下来讲解一个O(n^3)的解法，碉堡了。

算法步骤

1. 两层for循环实现。res记录最大累加和。首先由第一行求出这个子数组的最大累加和，然后第二行加到第一行上，同理求解加上去之后的子数组最大累加和，这个过程知道最后一行。
2. 然后不用管第一行了，从第二行开始，同理先求第二行，然后第三行加到第二行上，。。。，最后一行加到第二行上的最大累加和
3. 然后第三方开始，第四行开始。。。直到最后一行开始。搞定
   过程中注意更新全局最大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;
}