14320: 【原4320】最大偶数子区间

题目

题目描述

author: smallling 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4320

Description

给定一个长度为$n$的数组$a$，求和最大的长度为偶数的非空子区间的值。

Input Format

第一行一个数字$n$表示数组长度。 接下来一行$n$个数字表示数组$a$。 $2 \leq n \leq 10^6, -10^{6} \leq a_{i} \leq 10^{6}$

Output Format

一行一个数字表示答案

Sample Input

5
8 10 -8 8 10

Sample Output

20

ligongzzz's solution

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

long long sol(vector<long long> num) {
    int n = num.size();
    vector<long long> dp_data(n + 1, 0);

    long long ans = -1e9;
    for (int i = 0; i < n; ++i) {
        dp_data[i + 1] = max(dp_data[i] + num[i], num[i]);
        ans = max(ans, dp_data[i + 1]);
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin >> n;

    vector<long long> num(n);
    for (int i = 0; i < n; ++i) {
        cin >> num[i];
    }

    vector<long long> num1, num2;
    for (int i = 0; i + 1 < n; i += 2) {
        num1.emplace_back(num[i] + num[i + 1]);
    }
    for (int i = 1; i + 1 < n; i += 2) {
        num2.emplace_back(num[i] + num[i + 1]);
    }

    cout << max(sol(num1), sol(num2));

    return 0;
}

zqy2018's solution

#include <bits/stdc++.h>
#define REP(temp, init_val, end_val) for (int temp = init_val; temp <= end_val; ++temp)
using namespace std;
typedef long long ll;
int read(){
    int f = 1, x = 0;
    char c = getchar();
    while (c < '0' || c > '9'){if(c == '-') f = -f; c = getchar();}
    while (c >= '0' && c <= '9')x = x * 10 + c - '0', c = getchar();
    return f * x; 
}
int n, a[1000005];
void init(){
    n = read();
    for (int i = 1; i <= n; ++i)
        a[i] = read();
}
void solve(){
    ll sm = a[1] + a[2];
    ll ans = a[1] + a[2];
    ll mini0 = min(0, a[1] + a[2]), mini1 = a[1];
    REP(i, 3, n){
        sm += a[i];
        if (i & 1)
            ans = max(ans, sm - mini1), mini1 = min(mini1, sm);
        else 
            ans = max(ans, sm - mini0), mini0 = min(mini0, sm);
    }
    printf("%lld\n", ans);
}
int main(){
    init();
    solve();
    return 0;
}