Description
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
Output
Sample Input
4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2
Sample Output
15
Source
题目大意：给一个n*n的整数矩阵，找出一个子矩阵使其和最大。
解题思路：• 该题其实就是最大连续和问题在二维空间上的推广。
• 先来看一下一维的最大连续和问题：
给出一个长度为n的序列A1,A2,A3.....An,求一个连续子序列Ai,Ai+1,....Aj使得元素总和最大。
我们以temp[i]表示以Ai结尾的子段中的最大子段和。在已知temp[i]的情况下，求temp [i+1]的方法是：
如果temp[i]>0 temp [i+1]= temp[i]+ai(继续在前一个子段上加上ai),否则temp[i+1]=ai(不加上前面的子段);
也就是说 状态转移方程：temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i];
1 int getMax(int buf[107],int n){ 2 int temp[107],max=n*(-127); 3 memset(temp,0,sizeof(temp)); 4 for(int i=1;i<=n;i++){ 5 temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i]; 6 if(max<temp[i]) 7 max=temp[i]; 8 } 9 return max; 10 }//求n元素序列buf[]的最大连续和函数
|
• 对于本题可以暴力枚举i到j行，针对每一个i到j行的一列元素求和就将i到j行的2维情况转化为1维情况：如：
0 -2 -7 0
9 2 -6 2
-4 1 -4 7
-1 8 0 -2
取i=2,j=4,压缩为4（9 -4 -1），11（2 1 8），-10（-6 -4 0），7（2 7 -2）新的一维buf[]={4,11,-10,7},
然后求出buf[]的最大连续和就是2到4行范围内的最大矩阵的值。这样2层循环暴力所有i到j的情况取最大值即可！
1 #include<iostream> 2 using namespace std; 3 int rect[105][105];//2维矩阵 4 int n,Max;; 5 int buf[105];//中间1维矩阵 6 int getMax(){ 7 int Temp[105],max=n*(-127); 8 memset(Temp,0,sizeof(Temp)); 9 for(int i=1;i<=n;i++){ 10 Temp[i]=(Temp[i-1]>0 ? Temp[i-1] : 0 )+buf[i]; 11 if(max<Temp[i]) 12 max=Temp[i]; 13 } 14 return max; 15 }//求最大连续和 16 void read(){ 17 for(int i=0;i<n;i++) 18 for(int j=0;j<n;j++) 19 cin>>rect[i][j]; 20 }//读入 21 int solve(){ 22 Max=-127*n; 23 for(int i=0;i<n;i++){ 24 for(int j=i;j<n;j++){//2层循环暴力所有i到j组合 25 memset(buf,0,sizeof(buf));//压缩，2维变1维 26 for(int k=0;k<n;k++) 27 for(int L=i;L<=j;L++) 28 buf[k]+=rect[k][L]; 29 int d=getMax();//获得最大连续和 30 if(d>Max)Max=d;//更新Max值 31 } 32 } 33 return Max; 34 }//2维变1维暴力 35 int main(){ 36 while(cin>>n){ 37 read(); 38 solve(); 39 cout<<Max<<'\n'; 40 }return 0; 41 }
