最大子矩阵 杭电1559
/** * * 最大子矩阵 杭电15592014年上机真题
输入的数据在文件input.txt中读取，输出的结果存入output.txt中
* 思路：动态规划 状态dp[i][j]代表长i宽j的矩阵的元素和。 （dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]） 假设要求找出x长y宽的最大子矩阵 在i>=x且j>=y的矩阵中找的话， dp[i][j]就是包含a[i][j]元素的子矩阵的元素和， 则dp[i][j]-dp[i][j-y]-dp[i-x][j]+dp[i-x][j-y]就是 dp[i][j]中x长y宽的子矩阵的元素和（右下角元素为a[i][j]） https://yq.aliyun.com/articles/18949/ 感觉没见过的话 比较难 */ #include<stdio.h> #include<string.h> #include<algorithm> #define max(a,b) (a>b?a:b) using namespace std; int dp[1100][1100]; int MAX; int main() { int i,j,n,m,T,x,y; scanf("%d",&T); while(T--) { scanf("%d %d %d %d",&n,&m,&x,&y); MAX=0; memset(dp,0,sizeof(dp)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) { scanf("%d",&dp[i][j]); dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]; if(i>=x&&j>=y) { MAX=max(MAX,dp[i][j]-dp[i][j-y]-dp[i-x][j]+dp[i-x][j-y]); } } printf("%d\n",MAX); } return 0; }
换为文件输入输出如下：
#include<iostream>
#include<string.h>
#include<algorithm>
#include <fstream>
#include <sstream>
#define max(a,b) (a>b?a:b)
using namespace std;
int dp[1100][1100];
int MAX;
int main()
{
int i,j,n,m,T,x,y;
ifstream cinfile;
cinfile.open("input.txt",ios::in);
cinfile>>T;
// scanf("%d",&T);
while(T--)
{
// scanf("%d %d %d %d",&n,&m,&x,&y);
cinfile>>n>>m>>x>>y;
MAX=0;
memset(dp,0,sizeof(dp));
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
{
// scanf("%d",&dp[i][j]);
cinfile>>dp[i][j];
dp[i][j]+=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1];
if(i>=x&&j>=y)
{
MAX=max(MAX,dp[i][j]-dp[i][j-y]-dp[i-x][j]+dp[i-x][j-y]);
}
}
// printf("%d\n",MAX);
cinfile.close();
ofstream outfile;
outfile.open("output.txt",ios::out);
outfile<<MAX<<endl;
}
return 0;
} 2014年上机真题（专硕）
循环矩阵（第一列和最后一列是相邻的），求该矩阵中最大子矩阵（就是子矩阵中的元素和最大）；输入的数据在文件input.txt中读取，输出的结果存入output.txt中；
输入数据的格式如下：（中间只能一个空格，否则就不能存入数组中）
4
1 1 0 2
5 1 -3 1
2 2 -1 4
-7 -8 0 -5
武汉理工的输入格式：
4
1 1 0 2
5 1 -3 1
2 2 -1 4
-7 -8 0 -5
看上去有点像：从4阶矩阵中 选出最大子矩阵。
运用上述思想，可以吧x，y看为变量 进行 比较 。此处略。学会思想即可。
简易版：给定一个整型数组，数组中有正有负，求最大连续子序列的和。
本题可否看为特殊情况？？感觉这样处理的话 欠妥 暂略。
设f(n)表示以a[n]为子序列最后一个元素的最大和，则可以有下面的规则：
（1）当f(n-1)<0时，f(n)=a[n];
（2）当n!=0且f(n-1)>0时，f(n)=f(n-1)+a[n]。
用一个nGreatestNum来记录最大值，每次与f(n)进行比较，不断更新即可。
求一个n*n二维矩阵的最大子矩阵，maxSum。