首页 > 代码库 > 最大循环子序列和

最大循环子序列和

2024-09-21 03:18:14   204人阅读

 

解题关键：

子序列和最大的两种情况：（1）子序列位于序列中间，不中断

　　　　　　　　　　　　（2）子序列分散在序列两端，此时中间部分的序列和最小，（因为序列总和一定），因此取子序列的最小值t，然后总值-t即为所求；

　　　两种情况取max即可。

 

 1 #include<bits/stdc++.h> 2 #define INF 1000000  3 using namespace std; 4 typedef long long ll; 5 ll a[100002],n; 6 ll fun(){ 7     ll sum=0,max1=-INF; 8     for(ll i=0;i<n;i++){ 9         sum+=a[i];10         if(sum>max1) max1=sum;11         if(sum<0) sum=0;12     }13     return max1;14 }15 int main(){16     scanf("%lld",&n);17     ll sum=0;18     for(ll i=0;i<n;i++){19         scanf("%lld",a+i);20         sum+=a[i];21     }22     ll t1=fun();23     for(ll i=0;i<n;i++){24         a[i]=-a[i];25     }26     ll t2=fun();27     ll ans=max(t1,sum+t2);28     printf("%lld\n",ans);29 }

 

最大循环子序列和


联系
我们