C. Yarik and Array Codeforces Round 909 (Div. 3) 1899C

Problem - C - Codeforces

题目大意：有一个长度为n的数组a，合法子串应满足其中每两个相邻数奇偶性都不同，求所以合法子串中子串中元素和最大的子串，输出这个和

1<=n<=2e5;-1e3<=a[i]<=1e3

思路：首先考虑忽略奇偶性限制怎么求最大子串和，首先我们初始化答案ans为数组中所有数的最大值，然后我们遍历数组同时记录当前选择子串的元素和sum，对于数组中的每一个数，如果当前的sum已经小于0了，那就重置sum为当前数，因为如果当前数为正的，显然应该直接换，如果是负的，加上只会更小，除此情况之外就直接加上当前数即可。

        考虑奇偶性条件，也就是当奇偶性不满足的时候，sum也要重置为当前数，因为已经不合法了，所以多加一个和前一个数记起来是偶数就重置的条件即可

#include
//#include<__msvc_all_public_headers.hpp>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const ll MOD = 1e6 + 7;
ll n;
ll a[N];
void init()
{
 
}
void solve()
{
    cin >> n;
    init();
    ll ans = -0x7fffffff;//注意初始化的值
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        ans = max(ans, a[i]);
    }   
    ll sum = 0;
    for (int i = 1; i <= n; i++)
    {
        if (sum < 0 || (i>1&&abs(a[i] + a[i - 1]) % 2 == 0))
        {//当前和<0，或者和上一个数奇偶性相同
            sum = a[i];
        }
        else
        {//其他情况直接加上
            sum += a[i];
        }
        ans = max(sum, ans);//维护最大值
    }
    cout << ans;
    cout << '\n';
}
 
int main()
{
    
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}