本文共 1007 字，大约阅读时间需要 3 分钟。

题目来源:HNUCM-OJ

最大字段和模板

#include
   
    using namespace std;const int maxn=100+5;int dp[maxn];int a[maxn];int n;void solve(){
       dp[0]=a[0];    int maxsum=dp[0];    for(int j=1;j
    
     >n){
           for(int i=0;i
     
      >a[i];        solve();    }    return 0;}
     
    
   

求出最大子段和，以及子段的起始位置和结束位置

#include
   
    #include
    
     using namespace std;const int maxn=100000+8,INF=0x3f3f3f3f;int a[maxn],dp[maxn];int k=1,t,n;int main(){
       cin>>t;    while(t--)    {
           cin>>n;        for(int i=0;i
     
      >a[i];        int ss=0,en=0;        int x=0,y=0;        dp[0]=a[0];        int maxsum=dp[0];        for(int i=1;i
      
       =0)            {
                   dp[i]=dp[i-1]+a[i];                en=i;            }            else            {
                   dp[i]=a[i];                ss=en=i;            }            maxsum=max(maxsum,dp[i]);            x=ss+1;            y=en;        }        cout<<"Case "<
       
        <<":"<
       
      
     
    
   

学如逆水行舟，不进则退

转载地址：https://chocolate.blog.csdn.net/article/details/99233884 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！