给定一个无序矩阵，其中元素可正，可负，可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;
}
