帕绍网站建设,设计签名的小程序,服务器iis搭建网站,丹东做网站题目#xff1a;
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵#xff0c;你的任务是找到最大的非空(大小至少是1 1)子矩阵。
比如#xff0c;如下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。 …题目
已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵你的任务是找到最大的非空(大小至少是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(0N≤100)。再后面的若干行中依次(首先从左到右给出第一行的N个整数再从左到右给出第二行的N个整数……)给出矩阵中的N2个整数整数之间由空白字符分隔(空格或者空行)。已知矩阵中整数的范围都在[−127,127]。
【输出】 输出最大子矩阵的大小。
【输入样例】 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 【输出样例】 15
题意
找出梓矩阵最大和
思路 暴力模拟就是就是遍历求x1-x2行最值再遍历y1-y2列的最值 四层循环容易超时 -只看一行求最值就是最大连续子序列但是有很多行现在求未知连续的k行的矩阵所以就需要遍历1-2,1-3,1-4,2-3,2-4行 求矩阵和所以利用前缀和的知识可以累加前一行的数据直到最后一行要求区间K行的子矩阵遍历即可-即要求k行直接压缩成一维数组变成了一个一维数组的最长子序列问题 确定状态/选择累加行/列以后直接利用最大字段和的做法 dp[i] max(dp[i-1]k,dp[i]) 确定状态转移方程 边界条件 -①dp都初始化为0每次遍历完两行求出矩阵和计算了dp数组后求出当前的最值dp初始化一下。 ②存储最值的变量应该初始化-128 因为数据范围在【-127127】。 ③遍历时后一行减去前一行所以i 为【1n】,j为【1n】,j不能是【i1n】,因为有可能矩阵第一行就是有最值
数据约束
无
注意
①数组边界/遍历范围要注意 ②数据初始化要注意数据边界
参考代码一
#includebits/stdc.h
#define N 105
using namespace std;
int a[N][N],dp[N],ans-128; //初始化。。。。。。。。。。 int main(){int n;cinn;for(int i1;in;i){for(int j1;jn;j){cina[i][j];a[i][j] a[i-1][j];//各行的值累加 }} for(int i1;in;i){ //开始行 for(int ji;jn;j){ //结束行 for(int k1;kn;k){ //处理两行之前列的数据-做最大连续子序列 dp[k] a[j][k]-a[i-1][k];dp[k] max(dp[k],dp[k-1]a[j][k]-a[i-1][k]); //选择两行 并处理dp数组ans max(ans,dp[k]); }memset(dp,0,sizeof(dp));}} coutans;return 0;}参考代码二
#includebits/stdc.h
#define N 105
using namespace std;
N],dp[N],ans-128; //初始化。。。。。。。。。。 int main(){int n;cinn;for(int i1;in;i){for(int j1;jn;j){cina[i][j];a[i][j] a[i][j-1];//各列的值累加}} for(int i1;in;i){ //开始列 for(int ji;jn;j){ //结束列 不能从第二行开始不然第一行怎么办 memset(dp,0,sizeof(dp));for(int k1;kn;k){ //处理两列之前列的数据-做最大连续子序列 dp[k] a[k][j]-a[k][i-1];dp[k] max(dp[k],dp[k-1]a[k][j]-a[k][i-1]); //选择两行 并处理dp数组ans max(ans,dp[k]); }}} coutans;return 0;}
