4
#yyds干货盘点# 动态规划专题：最大子矩阵
source link: https://blog.51cto.com/u_15488507/5794260
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 动态规划专题：最大子矩阵
精选 原创1.简述：
描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 比如，如下4 * 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。
输入描述：
输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。 再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N2个整数，整数之间由空白字符分隔（空格或者空行）。 已知矩阵中整数的范围都在[-127, 127]。
输出描述：
输出最大子矩阵的大小。
示例1
4
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
2.代码实现：
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;
}
}
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;
}
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK