蓝桥杯-PREV26-最大子阵
问题描述 给定一个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。解题思路 刚开始只想到把多维矩阵转化为一维矩阵，进行求解。想法还是太单纯了讷~ 后来参考蓝桥杯-最大子阵 动态规划后来参考这篇文章，可算理解了解题的思路，整个从一维到多维的推导，讲得超详细哦~ #include<iostream> #include<algorithm> #include<cstring> using namespace std; int main(){ int n,m; cin>>n>>m; int num[505][505]={0}; int dp[505]; int temp[505]; //一维数组 for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ cin>>num[i][j]; } } int sum=num[1][1]; for(int i=1;i<=n;i++){ memset(temp,0,sizeof(temp)); for(int j=i;j<=n;j++){//n*m矩阵，两层循环来控制要压缩的第i行和第j行之间的元素 for(int k=1;k<=m;k++){ temp[k]+=num[j][k]; //△ } memset(dp,0,sizeof(dp)); dp[1]=temp[1]; for(int u=2;u<=m;u++){//求出一维数组的最大连续子序列和 dp[u]=max(dp[u-1]+temp[u],temp[u]); if(dp[u]>sum) sum=dp[u]; } } } cout<<sum<<endl; return 0; }