一般最大子段和 题目链接 hdu1003
原本对于题目来说，应该计算所有的子序列的和，然后比较得到最后的值。 这样做的话是会超时的。
可以用分治法和动态规划来做。 动态规划可以这样想。 d[i] 是以 a[i] 结尾的最大子序列的和。 d[i] = max { d[i-1]+a[i], a[i] } 然后记录最大值就可以了。
#include<iostream> #include<cstring> #include<cstdio> using namespace std; const int INF=1e9+7; const int maxn=1e5+5; int a[maxn],b[maxn]; int main() { int T,Case=1; scanf("%d",&T); while(T--){ if(Case>1) printf("\n"); int n; scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); a[0]=0,b[0]=0; for(int i=1; i<=n; i++){ if(b[i-1]>=0) b[i]=b[i-1]+a[i]; else b[i]=a[i]; } // for(int i=1 ;i<=n; i++){ // printf("%d ",b[i]); // } // printf("\n"); int maxSum=-INF, sit=1; for(int i=1; i<=n; i++){ if(b[i]>maxSum) { maxSum=b[i]; sit=i;} } int sit_2=sit; for(int i=sit-1; i>=1; i--){ if(b[i]>=0) sit_2--; else break; } printf("Case %d:\n",Case++); printf("%d %d %d\n",b[sit],sit_2,sit); } return 0; } ****************************************************************************************************** #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int INF=1e9+7; const int maxn=1e5+5; int a[maxn]; int Max_sum(int x, int y) { if(y-x==1) return a[x]; int mid=(x+y)/2; int xx=Max_sum(x,mid); int yy=Max_sum(mid,y); int ML=-INF,MR=-INF; int sumL=a[mid-1]; for(int i=mid-2; i>=x; i--){ sumL+=a[i]; ML=max(ML,sumL); } int sumR=a[mid]; for(int i=mid+1; i<y; i++){ sumR+=a[i]; MR=max(MR,sumR); } int xy=ML+MR; xx=max(xx,yy); xx=max(xx,xy); return xx; } int main() { int T,Case=1;; cin>>T; while(T--){ if(Case>1) cout<<endl; int n; cin>>n; for(int i=0; i<n; i++){ cin>>a[i]; } cout<<"Case "<<Case++<<":"<<endl; cout<<Max_sum(0,n)<<endl; } return 0; }最大M子段和
最大M子段和是最大子段和的推广。 给 n 个正整数组成的序列，以及一个正整数m， 求该序列中m个不相交的子段，使其总和最大。 首先定义状态转移方程。 设b（i，j） 表示数组 a 的前 j 项中 i 个子段和的最大值，且第 i 个子段包含 a[ j ] (保证现在的状态）。
接下来就要获得b的递归形式了。按照组合数学中经常用来分析序列的方式，将 的第 i 个子段的形成分成两种情况：一种是只包含a[ j ] 的，一种是不只包含 a[ j ] 的。 对于后者而言，b(i,j) 是b(i,j-1) 与a[j] 的和，因为只有这样才能保证其第 i 子段以 a[j] 结尾 而不仅仅只有一个a[j] ， 同时， b(i, j-1) 已经确定了 i 个以 a[j-1] 结尾的子段，所以不需要增加子段的个数，只需要将a[j] 加到已有子段上即可。 对于前者， 已经确定了 b(i,j) 的 i 个子段中的 第 i 个子段，需要在前 j-1 个元素中再确定 i-1个子段，这 i-1 个子段可以是以任何元素（下标小于j）结尾的，但要求是其中和最大的。
b(i, j) = max { b( i , j-1) + a[ j] , b(i-1 , t) + a[ j ] } (i-1 <= t < j) 现在进行优化
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define ll long long const int INF=1e9+7; const int maxn=1e6+5; int a[maxn]; ll MAX[maxn],dp[maxn]; int max(int a, int b) { return a>b?a:b; } int main() { int m,n; while(~scanf("%d%d",&m,&n)) { for(int i=1; i<=n; i++){ scanf("%d",&a[i]); } memset(dp,0,sizeof(dp)); memset(MAX,0,sizeof(MAX)); ll maxSum; for(int i=1; i<=m; i++){ maxSum=-INF; for(int j=i; j<=n; j++){ dp[j]=max(dp[j-1]+a[j],MAX[j-1]+a[j]); MAX[j-1]=maxSum; maxSum=max(maxSum,dp[j]); } } printf("%lld\n",maxSum); } return 0; }再给大家介绍一种子段和的问题
题目链接 hdu 1081
这是一道矩阵子段和的问题。
因为直接计算的话会有（n*n*n*n）的时间，于是乎必须优化一下， 我们计算出 第 1 1 2 1 2 3 1 2 3 4 2 2 3 2 3 4 3 3 4 4 行 的数的和，然后再用一维的计算方法来计算。 此时的时间复杂度是（n*(n-1)/2 *n)
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define ll long long const int INF=1e9+7; const int maxn=120; int a[maxn][maxn]; int b[maxn]; int r; int max(int i, int j) { return i>j?i:j; } int Sum(int n) { int sum=-INF, res=0; for(int j=1; j<=n; j++){ if(res>0) res+=b[j]; else res=b[j]; if(res>sum) sum=res; } return sum; } int init(int n) { int res=-INF; r=1; for(int i=1; i<=n; i++){ memset(b, 0, sizeof(b)); for(int j=i; j<=n; j++){ for(int k=1; k<=n; k++){ b[k]+=a[j][k]; } res=max(res,Sum(n)); } } return res; } int main() { int n; while(~scanf("%d",&n)){ for(int i=1; i<=n ;i++) { for(int j=1; j<=n; j++){ scanf("%d", &a[i][j]); } } printf("%d\n",init(n)); } return 0; }