题解 | #最大子矩阵#
最大子矩阵
http://www.nowcoder.com/practice/a5a0b05f0505406ca837a3a76a5419b3
本题目类似于柱状图中最大矩形，不过那一题使用单调栈做的（只有0和1），本题的话也可以用类似的思路，遍历矩形的行的起点和终点组合，然后相当于就是求解最大连续子数组和，最后取全局最大。
import java.util.*;
public class Main{
public static void main(String []args){
Scanner input=new Scanner(System.in);
int n=input.nextInt();
int [][]num=new int[n][n];
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
num[i][j]=input.nextInt();
}
}
int max=Integer.MIN_VALUE;
for(int i=0;i<n;i++){
int []tmp=new int[n];
for(int k=i;k<n;k++){
for(int j=0;j<n;j++){
tmp[j]+=num[k][j];
}
max=Math.max(max,new Main().getMax(tmp));
}
}
System.out.println(max);
}
public int getMax(int[]arr){
int n=arr.length;
if(n==0){
return arr[0];
}
int max=arr[0];
int []dp=new int[n];
dp[0]=arr[0];
for(int i=1;i<n;i++){
dp[i]=Math.max(dp[i-1]+arr[i],arr[i]);
max=Math.max(max,dp[i]);
}
return max;
}
}
