# 最大子段和问题-动态规划

xiaoxiao2021-03-01  10

#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; }

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; }

#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; }