邹老师的第一门课上小测了最大子矩阵的问题，课堂上只想到了O(n^2*m^2)的算法
后来翻《编程之美》的时候翻到了这道题...今天下午研究了一下,到OJ上切了几道题,熟悉了动态规划在这个问题中的应用.
一.最大子段和
书上已经将这种思想讲的很透彻,对基本的最大子段和的练习可以参照hdu1003题http://acm.hdu.edu.cn/showproblem.php?pid=1003,唯一的一点变形是这道题要求求出最大字段的起始位置和终止位置.
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #define INF 0x3f3f3f3f 7 using namespace std; 8 const int maxn=100005; 9 int map[maxn]; 10 int ans; 11 int begin; 12 int end; 13 int n; 14 void getmap() 15 { 16 for(int i=1;i<=n;i++) 17 { 18 cin>>map[i]; 19 } 20 } 21 void work() 22 { 23 int tempsum=0; 24 int tmpbegin=1; 25 for(int i=1;i<=n;i++) 26 { 27 tempsum+=map[i]; 28 if(tempsum>ans) 29 { 30 ans=tempsum; 31 begin=tmpbegin; 32 end=i; 33 } 34 if(tempsum<0) 35 { 36 tempsum=0; 37 tmpbegin=i+1; 38 } 39 40 } 41 } 42 43 int main() 44 { 45 int T; 46 cin>>T; 47 for(int tt=1;tt<=T;tt++) 48 { 49 ans=-INF; 50 cin>>n; 51 getmap(); 52 work(); 53 cout<<"Case "<<tt<<":"<<endl; 54 cout<<ans<<" "<<begin<<" "<<end<<endl; 55 if(tt<T) 56 { 57 cout<<endl; 58 } 59 } 60 return 0; 61 }
关于最大子段和有一种变形是最大m子段和,http://acm.hdu.edu.cn/showproblem.php?pid=1024,就是在原有的基础上求m段子段的和,这里建立动态规划方程,dp[i][j]表示前j个数(包括第j个数)组成i段的和的最大值,那么根据第j个数是否独立成组得到转移方程为dp[i][j]=max(dp[i-1][j-1]+a[j],dp[i-1][k]+a[j]),0<k<j,这里dp[i][]只和dp[i-1][]有关,用一维数组就可以表示,同时dp[i-1][k]表示1~j-1中构成i-1组的最大值,即前一组的值,那么可以在循环中求出,所以复杂度为O(n*m)
1 /* 2 dp[i][j]前j个数(包括第j个数,组成i组的和的最大值 3 dp[i][j]=max(dp[i-1][j-1]+map[j],dp[i-1][k]+map[j]),0<k<j 4 即根据第j个数是否单独成组划分状态 5 前i组仅与前i-1组有关,这里用一维数组就好 6 而dp[i-1][k]其实就是上一组中从0-j-1中划分为i-1组的最大值 7 */ 8 #include<iostream> 9 #include<cstdio> 10 #include<cstring> 11 #include<cstdlib> 12 #include<algorithm> 13 #define INF 0x3f3f3f3f 14 using namespace std; 15 const int maxn=1000005; 16 __int64 map[maxn]; 17 __int64 dp[maxn]; 18 __int64 prev[maxn]; 19 __int64 ans; 20 int m; 21 int n; 22 void getmap() 23 { 24 dp[0]=0; 25 prev[0]=0; 26 for(int i=1;i<=n;i++) 27 { 28 scanf("%I64d",&map[i]); 29 dp[i]=0; 30 prev[i]=0; 31 } 32 } 33 void work() 34 { 35 for(int i=1;i<=m;i++) 36 { 37 ans=-INF; 38 for(int j=i;j<=n;j++) 39 { 40 dp[j]=max(dp[j-1],prev[j-1])+map[j]; 41 prev[j-1]=ans; 42 ans=max(ans,dp[j]); 43 } 44 } 45 } 46 int main() 47 { 48 while(scanf("%d%d",&m,&n)!=EOF) 49 { 50 getmap(); 51 work(); 52 printf("%I64d\n",ans); 53 } 54 return 0; 55 }
根据这道题那么poj2593,http://poj.org/problem?id=2593,就很容易解决了...就是将m替换为两段就好
1 /* 2 dp[i][j]前j个数(包括第j个数,组成i组的和的最大值 3 dp[i][j]=max(dp[i-1][j-1]+map[j],dp[i-1][k]+map[j]),0<k<j 4 即根据第j个数是否单独成组划分状态 5 前i组仅与前i-1组有关,这里用一维数组就好 6 而dp[i-1][k]其实就是上一组中从0-j-1中划分为i-1组的最大值 7 */ 8 #include<iostream> 9 #include<cstdio> 10 #include<cstring> 11 #include<cstdlib> 12 #include<algorithm> 13 #define INF 0x3f3f3f3f 14 using namespace std; 15 const int maxn=1000005; 16 int map[maxn]; 17 int dp[maxn]; 18 int prev[maxn]; 19 int ans; 20 int m; 21 int n; 22 void getmap() 23 { 24 dp[0]=0; 25 prev[0]=0; 26 for(int i=1;i<=n;i++) 27 { 28 scanf("%d",&map[i]); 29 dp[i]=0; 30 prev[i]=0; 31 } 32 } 33 void work() 34 { 35 for(int i=1;i<=m;i++) 36 { 37 ans=-INF; 38 for(int j=i;j<=n;j++) 39 { 40 dp[j]=max(dp[j-1],prev[j-1])+map[j]; 41 prev[j-1]=ans; 42 ans=max(ans,dp[j]); 43 } 44 } 45 } 46 int main() 47 { 48 while(scanf("%d",&n)!=EOF&&n) 49 { 50 m=2; 51 getmap(); 52 work(); 53 printf("%d\n",ans); 54 } 55 return 0; 56 }
二.最大子矩阵
最大子矩阵的算法就是将第k列中第i行到j行的数的和求出,然后套用一维的算法就好
我拿poj1050,http://poj.org/problem?id=1050,做了练习
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<algorithm> 6 #define INF 0x3f3f3f3f 7 using namespace std; 8 const int maxn=105; 9 int map[maxn][maxn]; 10 int sum[maxn][maxn]; 11 int ans; 12 int n; 13 void getmap() 14 { 15 for(int i=1;i<=n;i++) 16 { 17 for(int j=1;j<=n;j++) 18 { 19 cin>>map[i][j]; 20 } 21 } 22 } 23 void getsum() 24 { 25 memset(sum,0,sizeof(sum)); 26 for(int i=1;i<=n;i++) 27 { 28 for(int j=1;j<=n;j++) 29 { 30 sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+map[i][j]; 31 } 32 } 33 } 34 void work() 35 { 36 ans=-INF; 37 for(int i=1;i<=n;i++) 38 { 39 for(int j=i;j<=n;j++) 40 { 41 int start=sum[j][n]-sum[i-1][n]-sum[j][n-1]+sum[i-1][n-1]; 42 int all=start; 43 for(int k=n-1;k>=1;k--) 44 { 45 if(start<0) 46 { 47 start=0; 48 } 49 start+=sum[j][k]-sum[i-1][k]-sum[j][k-1]+sum[i-1][k-1]; 50 all=max(all,start); 51 } 52 ans=max(ans,all); 53 } 54 } 55 } 56 int main() 57 { 58 while(cin>>n) 59 { 60 getmap(); 61 getsum(); 62 work(); 63 cout<<ans<<endl; 64 } 65 return 0; 66 }
暂时只能想到这些，以后遇到该问题的变形，比如像课后扩展那样对于矩阵可以首尾相连，二维扩展到三维、四维等等的问题，我会继续在这里更新。