历届试题 最大子阵
问题描述 给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。
其中，A的子矩阵指在A中行和列均连续的一块。 输入格式 输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。 接下来n行，每行m个整数，表示矩阵A。 输出格式 输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。 样例输入 3 3 -1 -4 3 3 4 -1 -5 -2 8 样例输出 10 样例说明 取最后一列，和为10。 数据规模和约定 对于50%的数据，1<=n, m<=50； 对于100%的数据，1<=n, m<=500，A中每个元素的绝对值不超过5000。
解题思路： 可以转化为求最大子序列 的问题。 第一映像是暴力枚举，不过显然会超时，然后就想到了DP。其实因为矩阵肯定是对齐的，所以如我们将两行加起来求最大子数组就可以得到一个行数为2的子矩阵。所以问题就转化成了求一个数组的最大子数组和。然后就是枚举第i行到第j行相加得到的数组了。注意res的值不能设为0，因为可能最后的结果是负数。 最大子序列和问题的思路在如下链接： http://blog.csdn.net/qq_30091945/article/details/59113550
Java代码:
import java.util.Arrays;
import java.util.Scanner;
public class Main {
static int[] dp = new int[600];
static int[][] num = new int[600][600];
static int N;
static int M;
static int MAX = Integer.MIN_VALUE;
public static int GetMax(int m){
int max = dp[1];
int tmp = 0;
for ( int i = 1 ; i <= m ; i++){
if ( tmp > 0 ){
tmp += dp[i];
}else{
tmp = dp[i];
}
max = Math.max(max, tmp);
}
return max;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner in = new Scanner(System.in);
N = in.nextInt();
M = in.nextInt();
for (int i = 1 ; i <= N ; i++){
for(int j = 1 ; j <= M ; j++){
num[i][j] = in.nextInt();
}
}
for ( int i = 1 ; i <= N ; i++){
Arrays.fill(dp, 0);
for ( int j = i ; j <= N ; j++){
for ( int k = 1 ; k <= M ; k++){
dp[k] += num[j][k];
}
MAX = Math.max(MAX, GetMax(M));
}
}
System.out.print(MAX);
in.close();
}
}
(PS:永远解决不了的问题，Java永远要超时，给那些参加蓝桥杯的同学们，不要学我一样学Java了，尽量用C++吧。)
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
