即日起在codingBlog上分享您的技术经验即可获得积分,积分可兑换现金哦。

河工大校赛 最大子段和

编程语言 fanhansheng 10℃ 0评论

1266: 最大子段和


时间限制: 1 秒 内存限制: 64 MB


提交: 395 解决: 99


提交 状态


题目描述

一个大小为n的数组a1到an(−10^4≤ai≤10^4)。请你找出一个连续子段,使子段长度为奇数,且子段和最大。

输入

第一行为T(1≤T≤5),代表数据组数。


之后每组数据,第一行为n(1≤n≤10^5),代表数组长度。


之后一行n个数,代表a1到an。

输出

每组数据输出一行,表示满足要求的子段和最大值


样例输入

1


4


1 2 3 4


样例输出

9

思路: 最大子段和, 分俩遍找最大值, 有可能开头序号为1, 也可能为2, 再特判一下n<=2的情况。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define mem(a) memset(a, 0, sizeof(a))
using namespace std;
typedef pair<int, int> Pii;
typedef long long LL;
const int MAXN = 100005;
const int inf = 0x3f3f3f3f;
const int Mod = 100000000;
inline int read()
{
    int f=1, x=0;
    char ch = getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}
int dp[MAXN];
int a[MAXN];
int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        mem(dp);
        for(int i=1; i<=n; ++i)
        {
            scanf("%d", &a[i]);
            dp[i]=a[i];
        }
        int Max1=a[1];
        for(int i=3; i<=n; i+=2)
        {
            if(dp[i]2]+a[i-1]+a[i])
            {
                dp[i]=dp[i-2]+a[i-1]+a[i];
                dp[i]=dp[i-2]+a[i-1]+a[i];
            }
            Max1=max(dp[i], Max1);
        }
        int Max2=-inf;
        if(n>=2)
        Max2=a[2];
        for(int i=2; i<=n; i+=2)
        {
            if(dp[i]2]+a[i-1]+a[i]&&i-2>=1)
            {
                dp[i]=dp[i-2]+a[i-1]+a[i];
                dp[i]=dp[i-2]+a[i-1]+a[i];
            }
            Max2=max(dp[i], Max2);
        }
        printf("%d\n", max(Max1, Max2));
    }
    return 0;
}

转载请注明:CodingBlog » 河工大校赛 最大子段和

喜欢 (0)or分享 (0)
发表我的评论
取消评论

*

表情