题目描述
给定一个长度为 $n$ 的整数序列 $a_1,a_2,…,a_n$ 。
请你找到一个该序列的子序列,要求:
-
该子序列的所有元素之和必须是奇数。
-
在满足条件 1 的前提下,该子序列的所有元素之和应尽可能大。
输出你找到的满足条件的子序列的所有元素之和。
保证至少存在一个满足条件的子序列。
注意,子序列不一定连续。
输入格式
第一行包含一个整数 $n$ 。
第二行包含 $n$ 个整数 $a_1,a_2,…,a_n$ 。
输出格式
输出一个整数,表示满足条件的子序列的所有元素之和。
数据范围
前 $6$ 个测试点满足 $1 ≤ n ≤5$。
所有测试点满足 $1 ≤ n ≤ 10^5$,−$10^4 ≤ a_i ≤ 10^4$。
输入样例1
4
-2 2 -3 1
输出样例1
3
输入样例2
3
2 -5 -3
输出样例1
-1
算法1
(线性规划) $O(n)$
状态表示:
$f[i][0]$表示从$1$~$i$中子序列之和为奇数的最大值
$f[i][1]$表示从$1$~$i$中子序列之和为偶数的最大值
状态转移:
设序列中第i位为x
x为奇数时:
f[i][1] = max(f[i - 1][1], f[i - 1][0] + x);
f[i][0] = max(f[i - 1][0], f[i - 1][1] + x);
x为偶数时:
f[i][1] = max(f[i - 1][1], f[i - 1][1] + x);
f[i][0] = max(f[i - 1][0], f[i - 1][0] + x);
C++ 代码 (空间未优化)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, INF = 1e8;
int n;
int f[N][2];
int main()
{
scanf("%d", &n);
f[0][0] = -INF;
for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
if (x & 1)
{
f[i][1] = max(f[i - 1][1], f[i - 1][0] + x);
f[i][0] = max(f[i - 1][0], f[i - 1][1] + x);
}
else
{
f[i][1] = max(f[i - 1][1], f[i - 1][1] + x);
f[i][0] = max(f[i - 1][0], f[i - 1][0] + x);
}
}
printf("%d\n", f[n][0]);
return 0;
}
C++ 代码 (空间优化)
#include <iostream>
#include <algorithm>
using namespace std;
int n, x, t;
int f[2];
int main()
{
scanf("%d", &n);
f[0] = -1e8;
for (int i = 1; i <= n; i ++ )
{
scanf("%d", &x);
t = x & 1;
tie(f[1], f[0]) = tie(max(f[1], f[!t] + x), max(f[0], f[t] + x));
}
printf("%d\n", f[0]);
return 0;
}
算法2
(贪心) $O(n)$
-
当序列中所有正数和为奇数时,该和即为最优解
-
否则,要么加上一个最大负奇数,要么去掉一个最小负奇数,可以得到最优解
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100010, INF = 1e8;
int n;
int a[N];
int main()
{
scanf("%d", &n);
int a = -INF, b = INF, sum = 0;
for (int i = 1; i <= n; i ++ )
{
int x;
scanf("%d", &x);
if (x > 0) sum += x;
if (x & 1 && x < 0 && x > a) a = x;
if (x & 1 && x > 0 && x < b) b = x;
}
if (sum & 1) printf("%d\n", sum);
else printf("%d\n", max(sum + a, sum - b));
return 0;
}
动态规划空间未优化引自 $@anss2$ , 题解及评论
空间优化引自 $@釜底抽风$ , 代码及评论
贪心引自 $@yxc$ , 代码