ZOJ-1074* 跟值最大子矩阵
ZOJ-1074* 和值最大子矩阵
1074:给出一个N*N矩阵,求所有子矩阵中能达到的最大和值。
动态规划。矩阵是二维的,先降维,想象把矩阵压扁成一维数组。数组中每个值是原矩阵一列的和值。然后问题转化成和最大的连续子串问题。
求连续子串最大和值O(n)可解。从头扫描累和,遇负数和值则舍弃。因为负值成了接下来的负担。
求子矩阵要确定起始的行和终止的行。在相同起始行下,列和数组是增量计算的,避免了重复计算。
计算演示。 确定行范围,扩展列。 行向下扩展过程中列只需增量计算。
A B C A B C A B C A B C A B C
A B C A B C A B C A B C A B C
A B C A B C A B C A B C A B C
1074:给出一个N*N矩阵,求所有子矩阵中能达到的最大和值。
动态规划。矩阵是二维的,先降维,想象把矩阵压扁成一维数组。数组中每个值是原矩阵一列的和值。然后问题转化成和最大的连续子串问题。
求连续子串最大和值O(n)可解。从头扫描累和,遇负数和值则舍弃。因为负值成了接下来的负担。
求子矩阵要确定起始的行和终止的行。在相同起始行下,列和数组是增量计算的,避免了重复计算。
计算演示。 确定行范围,扩展列。 行向下扩展过程中列只需增量计算。
A B C A B C A B C A B C A B C
A B C A B C A B C A B C A B C
A B C A B C A B C A B C A B C
#include<stdio.h> #include<memory.h> #include<iostream> using namespace std; int matrix[100][100]; int colsum[100]; //计算连续字串最大和值,O(n) int findmaxsum(int *p,int N) { int currsum=0; int maxsum=p[0]; for(int i=0;i<N;i++) { currsum+=p[i]; if(currsum<0) currsum=0; else if(currsum>maxsum) maxsum=currsum; } return maxsum; } int main() { int N; cin>>N; for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin>>matrix[i][j]; int tmp; int max=matrix[0][0]; //起始行 for(int rs=0;rs<N;rs++) { //初始化 memset(colsum,0,100*sizeof(int)); //终结行 for(int re=rs;re<N;re++) { //列值增加,求区域和 for(int col=0;col<N;col++) { colsum[col]+=matrix[re][col]; tmp=findmaxsum(colsum,col+1); if(tmp>max) max=tmp; } } } cout<<max<<endl; }