DP10. 最大子矩阵
描述
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是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
输出:
15
C++14 解法, 执行用时: 4ms, 内存消耗: 296KB, 提交时间: 2018-07-08
#include<cstdio>
#include<cstring>
int n;
int a[110][110];
int b[110];
int main()
{
//printf("123\n");
while(scanf("%d",&n)!=EOF)
{
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
scanf("%d",&a[i][j]);
int Max = -32767;
for(int i=0; i<n; i++)
{
//数组b表示i~j行，对应列元素的和
//将二维动态规划问题转化为一维动态规划问题
memset(b, 0, sizeof(b));
for(int j=i; j<n; j++)
{
//下面是针对数组b求最大子段和的动态规划算法
int sum=0;
for(int k=0; k<n; k++)
{
b[k] += a[j][k];
sum += b[k];
if(sum>Max) Max = sum;
if(sum<0) sum=0;
}
}
}
printf("%d\n",Max);
}
return 0;
}
C 解法, 执行用时: 4ms, 内存消耗: 304KB, 提交时间: 2021-03-03
#include<stdio.h>
#include<string.h>
#define INF 1E9
int matrix[101][101];
int n,maxSum;
int buf[101];
int max(int a,int b){
return a>b?a:b;
}
int findMax(){
int i;
int M;
int dp[101]={0};
dp[0]=buf[0];
for(i=1;i<n;i++){
dp[i]=max(dp[i-1]+buf[i],buf[i]);
}
M=dp[0];
for(i=1;i<n;i++)
M=max(dp[i],M);
return M;
}
int main(){
int i,j,k;
while(scanf("%d",&n)!=EOF){
if(n<=0){break;}
maxSum=-INF;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&matrix[i][j]);
}
}
for(i=0;i<n;i++){
memset(buf,0,sizeof(buf));
for(j=i;j<n;j++){
for(k=0;k<n;k++){
buf[k]+=matrix[j][k];
}
maxSum=max(findMax(),maxSum);
}
}
printf("%d\n",maxSum);
}
}
C 解法, 执行用时: 4ms, 内存消耗: 304KB, 提交时间: 2019-02-17
#include<stdio.h>
#include<memory.h>
int sum[100];
int dp[100]={0};
int getResult(int n){
dp[0]=sum[0];
for(int i = 1;i<n;i++){
dp[i]=(dp[i-1]+sum[i])>sum[i]?(dp[i-1]+sum[i]):sum[i];
}
int max = -127;
for(int i = 0;i<n;i++){
if(dp[i]>max){
max =dp[i];
}
}
return max;
}
int main(){
int n;
int matrix[100][100];
while(scanf("%d",&n)!=EOF){
for(int i = 0;i<n;i++){
for(int j = 0;j<n;j++){
scanf("%d",&matrix[i][j]);
}
}
int ans = -127;
for(int i = 0;i<n;i++){
memset(sum,0,sizeof(sum));
for(int j = i;j<n;j++){
for(int k = 0;k<n;k++){
sum[k] += matrix[j][k];
}
int temp = getResult(n);
if(temp > ans){
ans = temp;
}
}
}
printf("%d\n",ans);
}
}
C 解法, 执行用时: 4ms, 内存消耗: 316KB, 提交时间: 2019-03-25
/*最大子矩阵和，思路：因为是二维的，倒是无法像一维那样dp解决
想到用压缩二维矩阵(就是从上往下加)成一维以题中给出的用例为例，按行压缩得到一个一维数组，然后
从左往右加过去，一旦sum<0从新累加， 等遍历完所有就能比出最大那个值了
*/
#include<stdio.h>
#include<string.h>
#define INF 1E9
int matrix[101][101];
int n,maxSum;//n是输入的矩阵大小，max保存着最大那个
int buf[101];//保存着每个压缩行的值
int max(int a,int b){
return a>b?a:b;
}
//常规的找最大连续子序列和操作
int findMax(){
int i;
int M;
int dp[101]={0};
dp[0]=buf[0];
for(i=1;i<n;i++){
dp[i]=max(dp[i-1]+buf[i],buf[i]);
}
M=dp[0];
for(i=1;i<n;i++)
M=max(dp[i],M);
return M;
}
int main(){
int i,j,k;
while(scanf("%d",&n)!=EOF){
if(n<=0){break;}
maxSum=-INF;//初始话最大值
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&matrix[i][j]);
}
}
//前面是输入矩阵操作
for(i=0;i<n;i++){
memset(buf,0,sizeof(buf));
/*
第一轮从第一行开始往下依次合并n-0行
第二轮从第二行开始往下依次合并n-1行
……
每一轮开始前buf都要重新置0
*/
for(j=i;j<n;j++){
for(k=0;k<n;k++){//这是表示列数
buf[k]+=matrix[j][k];
}
//对每次的buf进行一次是否最大比较
maxSum=max(findMax(),maxSum);
}
}
printf("%d\n",maxSum);
}
}
C 解法, 执行用时: 4ms, 内存消耗: 320KB, 提交时间: 2022-03-04
#include<stdio.h>
#include<string.h>
#define MAX(a,b)(a>b?a:b)
#define INF 0x3f3f3f3f
#define N 105
int nums[N][N];
int buf[N];
int n,max;
int findMax(buf[],n){
int i;
int result=buf[0];
int dp[n+1];
memset(dp, 0, sizeof(dp));
for(i=1;i<n+1;i++){
dp[i]=MAX(dp[i-1]+buf[i-1],buf[i-1]);
result = MAX(result, dp[i]); //更新最大连续子序列和
}
return result;
}
int main(){
int i,j,k;
while(scanf("%d",&n)!=EOF){
if(n<=0){
break;
}
max=-INF;
for(i=0;i<n;i++){
for(j=0;j<n;j++){
scanf("%d",&nums[i][j]);
}
}
for(i=0;i<n;i++){
memset(buf,0,sizeof(buf));
for(j=i;j<n;j++){
for(k=0;k<n;k++){
buf[k]+=nums[j][k];
}
max=MAX(findMax(buf,n), max);
}
}
printf("%d\n",max);
}
}