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

题目描述

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

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 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(){
for (int i = 1; i <= n; ++i)
}
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;
}