首页 > 代码库 > poj1050查找最大子矩阵和
poj1050查找最大子矩阵和
题目:
To the Max
Time Limit: 1000MS | Memory Limit: 10000K | |
Total Submissions: 48507 | Accepted: 25662 |
Description
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.
As an example, the maximal sub-rectangle of the array:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:
9 2
-4 1
-1 8
and has a sum of 15.
As an example, the maximal sub-rectangle of the array:
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
is in the lower left corner:
9 2
-4 1
-1 8
and has a sum of 15.
Input
The input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N^2 integers separated by whitespace (spaces and newlines). These are the N^2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 100. The numbers in the array will be in the range [-127,127].
Output
Output the sum of the maximal sub-rectangle.
Sample Input
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
Sample Output
15
题意:给你一个N*N的矩阵,求该矩阵的最大子矩阵和。
子矩阵和:该子矩阵中所以元素的和。
解决方法:
用第一个三维数组dp[k][i][j]存第k行 第i~j 列的和。 比如dp[3][1][5]表示从 "第3行第1列" 到 "第3行第5列" 的和。
用第二个三维数组sum[k][i][j]表示"dp[1][i][j]"到"dp[k][i][j]"的和。比如sun[4][2][5]表示前4行 所有第2~5列的和。 注意:所有的数据输出从下标1开始。
然后四层循环统计sum[k2][i][j]-sum[k1][i][j]的最大值。(1<=k1<=k2<=n)
代码:
#include <iostream> #include <cstring> using namespace std; int mmap[101][101]; //存矩阵 int dp[101][101][101]; //dp[k][i][j]存第k行 第i~j列的和。 比如dp[3][1][5]表示从 "第3行第1列" 到 "第3行第5列" 的和。 int sum[101][101][101]; //sum[k][i][j]表示"dp[1][i][j]"到"dp[k][i][j]"的和。比如sun[4][2][5]表示前4行 所有第2~5列的和。 注意:所有的数据输出从下标1开始。 int n; int main() { while(cin>>n) { memset(dp,0,sizeof(dp)); //数组初始化为0 memset(sum,0,sizeof(sum)); //矩阵数据输入 for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { cin>>mmap[i][j]; } } //计算dp数组 for(int k=1;k<=n;k++) //k表示第k行 { for(int j=1;j<=n;j++) //因为从i~j列所以j放在i的外层 { for(int i=1;i<=j;i++) { //统计从i~j列的和 int sum=0; for(int p=i;p<=j;p++) sum+=mmap[k][p]; dp[k][i][j]=sum; } } } //计算sum数组 for(int j=1;j<=n;j++) { for(int i=1;i<=j;i++) { for(int k=1;k<=n;k++) { //对应每组 i~j 列,前k行 所有的i~j列的元素的和 sum[k][i][j]+=(dp[k][i][j]+sum[k-1][i][j]); } } } int mmax=-1000000; for(int j=1;j<=n;j++) { for(int i=1;i<=j;i++) { //对应每组i~j列,统计每组 a~b 行的最大的和。 for(int b=1;b<=n;b++) { for(int a=1;a<=b;a++) { mmax=max(mmax,sum[b][i][j]-sum[a-1][i][j]); } } } } cout<<mmax<<endl; } return 0; }
poj1050查找最大子矩阵和
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。