104-最大和

内存限制:64MB 时间限制:1000ms 特判: No
通过数:51 提交数:151 难度:5

题目描述:

给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。 
例子：
0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2 
其最大子矩阵为：

9 2 
-4 1 
-1 8 
其元素总和为15。 

输入描述:

第一行输入一个整数n（0<n<=100）,表示有n组测试数据；
每组测试数据：
第一行有两个的整数r，c（0<r,c<=100），r、c分别代表矩阵的行和列；
随后有r行，每行有c个整数；

输出描述:

输出矩阵的最大子矩阵的元素之和。

样例输入:

复制

1
4 4
0 -2 -7 0 
9 2 -6 2 
-4 1 -4 1 
-1 8 0 -2 

样例输出:

15


基本思路是将二维转化为一维，即转化为求解一维数组中连续子序列的最大和问题。

 1 import java.util.Scanner;
 2 
 3 public class Main{
 4     //将二维降为一维(针对由第row1行到第row2行组成的矩阵，将该矩阵每一列相加，组成一维数组)
 5     public static int[] transToLine(int[][] a,int row1,int row2){
 6         int[] array=new int[a[0].length];
 7         for (int i = 0; i < a[0].length; i++) {//将第i列的元素求和
 8             int sum=0;
 9             for (int j = row1; j <= row2; j++) {
10                 sum+=a[j][i];
11             }
12             array[i]=sum;
13         }
14         return array;
15     }
16 
17     //求一维连续子序列最大和
18     public static int result(int[] a){
19         int[] d=new int[a.length];
20         int res=d[0]=a[0];
21         for (int i = 1; i < a.length; i++) {
22             d[i]=Math.max(d[i-1]+a[i],a[i]);
23             res=Math.max(res,d[i]);
24         }
25         return res;
26     }
27 
28     public static void main(String[] args) {
29         int n,r,c;
30         Scanner sc = new Scanner(System.in);
31         n = sc.nextInt();
32         while (n-->0){
33             r = sc.nextInt();
34             c = sc.nextInt();
35             int[][] a=new int[r][c];
36             for (int i = 0; i < r; i++) {
37                 for (int j = 0; j < c; j++) {
38                     a[i][j]=sc.nextInt();
39                 }
40             }
41             int res=-65535;
42             for (int row1 = 0; row1 < a.length; row1++) {
43                 for (int row2 = row1; row2 < a.length; row2++) {
44                     int[] array;
45                     array = transToLine(a, row1, row2);
46                     int result = result(array);
47                     res=Math.max(res,result);
48                 }
49             }
50             System.out.println(res);
51         }
52     }
53 }