首页 > 代码库 > dp/hdu 1003 Max Sum

dp/hdu 1003 Max Sum

2024-07-26 13:22:23   218人阅读

题目

　　给出一列数，求出最大的子段和，并输出起始点和结束点

分析

　　设d[i]为末尾数是i的最大和，我们可以得到

　　d[i-1]>=0时，d[i]=d[i-1]+a[i];

　　d[i-1]<=0时，d[i]=a[i];

　　i从1到n都算过一遍后，找出最大的d[i]，则此时的i为结束点。再从结束点倒着向前加，直到找到与答案相同的位置，记为起始点

Accepted Code

 1 /* 2     PROBLEM:hdu1003 3     AUTHER:NicoleLam 4     MEMO:dp 5 */ 6 #include<cstdio> 7 const int MAXN=100010; 8  9 int a[MAXN],d[MAXN];10 int main()11 {12     int tot;13     scanf("%d",&tot);14     for (int t=1;t<=tot;t++)15     {16         int n;17         scanf("%d",&n);18         for (int i=0;i<MAXN;i++){a[i]=0;d[i]=0;}19         for (int i=1;i<=n;i++) scanf("%d",&a[i]);20         d[1]=a[1];21         for (int i=2;i<=n;i++)22         {23             if (d[i-1]>=0) d[i]=d[i-1]+a[i];24             else d[i]=a[i];25         }26         int ans=d[1],ed=1;27         for (int i=2;i<=n;i++)28             if (ans<d[i])29             {30                 ans=d[i];31                 ed=i;32             }33         int temp=0,st=ed;34         for (int i=ed;i>0;i--)35         {36             temp+=a[i];37             if (temp==ans) st=i;38         }39         printf("Case %d:\n",t);40         printf("%d %d %d\n",ans,st,ed);41         if (t!=tot) printf("\n");42     }43     return 0;44 }

 

dp/hdu 1003 Max Sum


联系
我们