给定一个 n*mn \times mn*m 的矩阵 AAA, 求 AAA 中的一个非空子矩阵, 使这个子矩阵中的元素和最大. 其中, AAA 的子矩阵指在 AAA 中行和列均连续的一部分.
输入格式
输入的第一行包含两个整数 n,m(1≤n,m≤50)n,m(1 \leq n,m \leq 50)n,m(1≤n,m≤50), 分别表示矩阵 AAA 的行数和列数.
接下来 nnn 行, 每行 mmm 个整数, 表示矩阵 Ai,j(−1000≤Ai,j≤1000)A_{i,j}(-1000 \leq A_{i,j} \leq 1000)Ai,j?(−1000≤Ai,j?≤1000).
输出格式
输出一行, 包含一个整数, 表示 AAA 中最大子矩阵的元素和.
样例输入
- 3 3
- 2 -4 1
- -1 2 1
- 4 -2 2
样例输出
6
package 最大子阵;
- import java.util.Scanner;
public class 最大子阵 {
- /**
- * @param args
- */
- public static void main(String[] args) {
- // TODO Auto-generated method stub
- Scanner scan=new Scanner(System.in);
- int n=scan.nextInt();
- int m=scan.nextInt();
- int[][] arr=new int[n][m];
- for(int i=0;i<n;i++){
- for(int j=0;j<m;j++){
- arr[i][j]=scan.nextInt();
- }
- }
- int max=arr[0][0];
- for(int begini=0;begini<n;begini++){
- for(int endi=begini;endi<n;endi++){
- for(int beginj=0;beginj<m;beginj++){
- for(int endj=beginj;endj<m;endj++){
- int sum=0;
- for(int i=begini;i<=endi;i++){
- for(int j=beginj;j<=endj;j++){
- sum+=arr[i][j];
- }
- }
- if(sum>max&&sum!=0){
- max=sum;
- }
- }
- }
- }
- }
- System.out.println(max);
- }
- }
最大子阵
来源: http://www.bubuko.com/infodetail-2969547.html