给定一个无序矩阵，其中元素可正，可负，可0,给定k,求累加和小于等于k的最大子矩阵

[算法原型]http://www.jianshu.com/p/028055303e3b

思路：

其实和[子数组最大和]http://www.jianshu.com/p/3a555e316587
道理一样，假如能够求得一个一维数组的累加和小于等于k的最长子数组，那么这个问题也就出来了。（都是套路：由数组扩充到矩阵）

代码

 public static  int maxSubMatricSumLessThanK(int[][]arr,int num){
        int res=0;
        int[] s=null;
        for(int i=0;i<arr.length;i++){
            s=new int[arr[0].length];
            for(int j=i;j<arr.length;j++){
                for(int k=0;k<s.length;k++){
                    s[k]+=arr[j][k];
                }
                res=Math.max(res,maxLength(s,num)*(j-i+1));
            }
        }
        return res;
    }
    public static int maxLength(int[] arr,int k){
        if(arr==null||arr.length==0)
            return 0;
        int[] h=new int[arr.length+1];
        int sum=0;
        h[0]=sum;
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
            h[i+1]=Math.max(h[i],sum);
        }
        sum=0;
        int res=0;
        int pre=0;
        int len=0;
        for(int i=0;i<arr.length;i++){
            sum+=arr[i];
            pre=findFirstBiggerOrEqual(h,sum-k);
            len=pre==-1?0:i-pre+1;
            res=Math.max(res,len);
        }
        return res;
    }
    public static int findFirstBiggerOrEqual(int[] h,int num){
        int left=0;
        int right=h.length-1;
        int res=-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(h[mid]>=num){
                res=mid;
                right=mid-1;
            }
            else
                left=mid+1;
        }
        return res;
    }