CSU - 1529 Equator —— DP 最大连续和子序列

时间：2022-11-17 04:39:12

题目链接：http://acm.csu.edu.cn/csuoj/problemset/problem?pid=1529

题解：

一个加强版的最大连续和子序列，序列可以从末尾元素转到首元素。

分两种情况：

1.最大连续和不需要尾接首，直接dp出以a[i]为结尾的最大连续和ma[i]。

2.最大连续和需要尾接首，先dp出以a[i]为结尾的最小连续和mi[i]，然后再用总和sum减去mi[i],得到的即为减去中间部分的尾接首序列和（逆向思维）。最后再用max()取最大值。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 #define eps 0.0000001

 #define LNF (1<<60)

 typedef long long LL;

 const int inf = 0x3f3f3f3f;

 const int maxn = +;

 const int mod = 1e9+;

 LL a[maxn], ma[maxn], mi[maxn];

 int main()

 {

     int T, n;

     scanf("%d", &T);

     while(T--)

     {

         LL sum = ;

         scanf("%d",&n);

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

             scanf("%lld",&a[i]), sum += a[i];

         for(int i = ; i<=n; i++)//最大连续和

             ma[i] = max(ma[i-], 0LL) + a[i];

         for(int i = ; i<=n; i++)//最小连续和

             mi[i] = min(mi[i-], 0LL) + a[i];

         LL ans = ma[];

         for(int i = ; i<=n; i++)//寻找最大值

         {

             ans = max(ans, ma[i]);

             ans = max(ans, sum-mi[i]);

         }

         printf("%lld\n",ans);

     }

     return ;

 }

相关文章