一维问题：nyoj 44 子串和
链接：click here
题目大意：给定一整型数列{a1,a2…,an}，找出连续非空子串{ax,ax+1,…,ay}，，使得该子序列的和最大，其中，1<=x<=y<=n。
思路：m是元素总个数，sum是第一个元素，将当前的第一个元素作为最大值max,之后依次输入，检查sum<0？是的话更新sum为当前输入值：否则累加，最后比较这样每次步骤的最大值。
代码：
#include <stdio.h>#include <math.h>#include <string.h>#include <iostream>#include <algorithm>int main(){int n,m,q,max,sum;scanf("%d",&n);while(n–){max=0;scanf("%d",&m);scanf("%d",&sum);max=sum;while(m–){scanf("%d",&q);if(sum<0) sum=q;else sum+=q;if(sum>max) max=sum;}printf("%d\n",max);}return 0;}二维问题：nyoj 104 最大和
链接：click here
题目大意：给定一个由整数组成二维矩阵（r*c），现在需要找出它的一个子矩阵，使得这个子矩阵内的所有元素之和最大，并把这个子矩阵称为最大子矩阵。 例子：0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 其最大子矩阵为：9 2 -4 1 -1 8 其元素总和为15。
思路：
二维的问题，其实可以转化为一维的问题。首先我们要注意到二维子矩阵在选取的时候是个矩阵，联系一个我们经常会用到的技巧：需要频繁计算一个数据任意一个区间的和的时候，我们会预先把这个数组使用mapp[i]=mapp[i]+mapp[i-1]的方式把它记录的值变为数组到这个位置的和，这样的好处就是任意一个区间[i,j]的和就可转化为了mapp[i]-mapp[j-1]。在这里我们依然采用这样的技巧。我们把这个矩阵记录的值对于每个列向量都做上述改变。然后我们就发现，但我们选取任意的连续行进行组合的时候，这个行区间对于的列的值的和都可以用上述方法快速获得，那么对于每个列的和又会变为一个求一维连续区间最大和问题了。到此这个问题就可以以O(n^2)的复杂度解决了。代码：
#include <math.h>#include <stdio.h>#include <string.h>#include <iostream>#include <algorithm>const int maxn=102;int mapp[maxn][maxn];#define mem(a,b) memset(a,b,sizeof(a))int main(){int i,j,k,tt,T,r,c,max,temp;scanf("%d",&T);while(T–){mem(mapp,0);scanf("%d%d",&r,&c);for(i=1; i<=r; i++){for(j=0; j<c; j++){scanf("%d",&mapp[i][j]);mapp[i][j]+=mapp[i-1][j];}}for(i=1,tt=mapp[1][0]; i<=r; i++)for(j=i; j<=r; j++){for(k=max=0; k<c; k++){temp=mapp[j][k]-mapp[i-1][k];max=(max>=0?max:0)+temp;tt=max>tt?max:tt;}}printf("%d\n",tt);}return 0;}
爱情要完结的时候自会完结，到时候，你不想画上句号也不行。
