最大子段和

模版

int a[maxn],n;
int pre[maxn];
int dp[maxn]= {};
///输出子段起始点
while(scanf("%d",&n),n)
{
   for (int i=1; i<=n; i++)
       scanf("%d",&a[i]);
   memset(dp,-1,sizeof(dp));
   for (int i=1; i<=n; i++)
   {
       if (dp[i-1]<0)
       {
           pre[i]=i;
           dp[i]=a[i];
       }
       else
       {
           pre[i]=pre[i-1];
           dp[i]=dp[i-1]+a[i];
       }
   }
   int idx,mx=-1;
   for (int i=1; i<=n; i++)
       if (dp[i]>mx)
       {
           mx=dp[i];
           idx=i;
       }
   if (mx<0) printf("%d %d %d\n",0,a[1],a[n]); //所有值均小于零
   else printf("%d %d %d\n",mx,a[pre[idx]],a[idx]);
}

results matching ""

    No results matching ""