A25165. 交替序列提示信息：子序列：对于一个序列 a，删除其中 0 个或多个元素而不改变剩余元素的顺序，得到的序列称为 a 的子序列。例如：序列 a 为 {1，2，3，4，5}，则序列 {1}，{1，2，3}，{1，3，5} 等都可以称为序列 a 的子序列。
填空题
容易
知识点
题目描述
交替序列
提示信息：子序列：对于一个序列 a，删除其中 0 个或多个元素而不改变剩余元素的顺序，得到的序列称为 a 的子序列。
例如：序列 a 为 {1，2，3，4，5}，则序列 {1}，{1，2，3}，{1，3，5} 等都可以称为序列 a 的子序列。
题目描述：给定一个包含 n 个整数的序列 a，请从中找出一个满足以下条件的子序列：
（1）该子序列中相邻元素的正负号相反（如果第一个元素为正数，则第二个元素为负数，第三个元素为正数，以此类推。反之，如果第一个元素为负数，则第二个元素为正数，第三个元素为负数，以此类推）；
（2）该子序列长度最长；
（3）在满足以上条件的情况下，该子序列中的元素之和最大。
最后输出该子序列中的元素之和。
例如：n = 5；序列 a 为 {2，-1，-3，15，10}。
同时满足条件 1 和条件 2 的子序列有 {2，-1，15}，{2，-1，10}，{2，-3，15}，{2，-3，10}；
其中元素之和最大的子序列是 {2，-1，15}，和为 16。
输入描述：
第一行输入一个整数 n（1≤n≤2×10^5）；
第二行输入 n 个整数 ai（-10^9≤ai≤10^9，ai≠0），整数之间以一个空格隔开。
输出描述：
输出一个整数，表示满足题目要求的子序列的元素之和。
样例输入：
5
2 -1 -3 15 10样例输出：
16参考答案
#include <iostream>
using namespace std;
int n, a[10000], dp[10000], dps[10000];
int main() {
cin >> n;
for(int i = 0; i < n; i++) {
cin >> a[i];
}
int max_len = 0;
for(int i = 0; i < n; i++) {
dp[i] = 1;
dps[i] = a[i];
for(int j = 0; j < i; j++) {
if(a[i] * a[j] < 0) { //如果符号不同
dp[i] = max(dp[i], dp[j] + 1);
dps[i] = max(dps[i], dps[j] + a[i]);
}
}
max_len = max(max_len, dp[i]);
}
int ans = dps[0];
for(int i =0; i<n; i++) {
if(dp[i] == max_len && dps[i] > ans) {
ans = dps[i];
}
}
cout << ans << endl;
return 0;
}
上一题
下一题