（DP）HDU - 1003 Max Sum

这是一道DP入门题目，知识点是“最大连续子序列”

题目大意：给你一个长度为n的数字序列，取其中一段连续的序列，要求和最大；

分析：这是一道裸题，没有什么花里胡哨的东西，主要是写出状态转移方程
　　　　　　　　dp[i] = max{dp[i-1] + A[i], A[i]};
　　dp[i]是以i位置为结尾位置的最优解。

　　对于i位置上的A[i],一定对dp[i]做出了贡献。

　　对于i以前的位置，他们的最优解是dp[i-1],当dp[i-1]>=0时，dp[i-1]对dp[i]做出了贡献;反之，dp[i-1]对dp[i]有消极的作用；

我的错误：1.边界dp[1]忘记做了处理
　　　　 2.要每次更新起点，铁憨憨我直接把最后更新后的结果当结果了。。

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 using namespace std;

 const int Maxn =  + ;

 int T,n;

 int dp[Maxn];

 int main()

 {

     scanf("%d",&T);

     for(int t=;t<=T;t++)

     {

         scanf("%d",&n);

         for(int i=;i<=n;i++)

             scanf("%d",&dp[i]);

         int ans = dp[];//用边界对ans初始化

         int start = ,ends = ,fstart=;

         for(int i=;i<=n;i++)

         {

             if(dp[i-]>=)

                 dp[i] += dp[i-];

             else

                 start = i;//起点的更新不一定是最优解

             if(dp[i] > ans)

             {

                 ans = dp[i];

                 fstart = start;//在更新最优解的时候更新起点

                 ends = i;

             }

         }

         if(t!=) puts("");

         printf("Case %d:\n",t);

         printf("%d %d %d\n",ans,fstart,ends);

     }

     return ;

 }

巴特西

（DP）HDU - 1003 Max Sum

最新文章

热门文章