【题解】奇数求和

题意

给你一个长度为的数组，可以将其一段区间进行反转，问数组中所有下标为奇数的元素的和最大是多少。

题解

首先若反转的区间长度为奇数那么奇偶的位置实际上没有影响，所以若反转的长度为奇数那么没有贡献。则当考虑反转长度为偶数的区间，只需要判断哪一个区间内的偶数位置的数比奇数位置的数大即可，我们将偶数位置的数和前面一个奇数位置的数做差，或者是将奇数位置和他前面的偶数位置的数做差，并对这两个做差得到的区间求最大子段和即可。这里得到的就是反转区间所能得到的最大贡献，加上原先的奇数和，就是最后的答案了。

复杂度

时间复杂度

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int a[N];
vector<int>b;
vector<int>c;
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n;
        long long num=0,sum=0,maxn=0;
        b.clear();
        c.clear();
        scanf("%d",&n);
        for(int i=0; i<n; i++)
        {
            scanf("%d",&a[i]);
            if(i%2!=0)
            {
                b.push_back(a[i]-a[i-1]);
            }
            else
            {
                num+=a[i];
                c.push_back(a[i-1]-a[i]);

            }
        }
        for(int i=0; i<b.size(); i++)
        {
            sum+=b[i];
            maxn=max(maxn,sum);
            if(sum<0)
            {
                sum=0;
            }
        }
        sum=0;
        for(int i=0; i<c.size(); i++)
        {
            sum+=c[i];
            maxn=max(maxn,sum);
            if(sum<0)
            {
                sum=0;
            }
        }
        printf("%lld\n",maxn+num);
    }
    return 0;
}