正经题解｜接力长跑

题目大意

再给定序列中，找满足条件的连续数值最大为多少。

题目思路

其中连续的数字要想累加，需要满足前后两个数的奇偶性想法才可以累加。同时因为学生们能力值存在负数，所以还需要考虑是否放弃该同学即前面内容。在整个过程中全程判断是否存在更优的情况，如果存在及时记录即可。该问题属于线性动态规划经典问题变形。

我们可以设定学生状态为$dp[i]$，从而列出以下状态转移方程

• $a_i$ % $2$ != $a_{i-1}$ % $2$ : $dp[i] = max(a[i],dp[i-1] + a[i])$

时间复杂度分析

该算法的时间复杂度主要集中在遍历序列中每一项，因此是 $O(n)$ 的复杂度。

代码演示

#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
int f[N];
int main(){
	int T;
	cin >> T;
	while(T--){
		int n;
		cin >> n;
		long long sum = 0, max_N = -1e7;
		long long a, last = 0;
		cin >> a;
		last = a;
		sum = a;
		max_N = a; 
		for(int i = 2;i <= n;i++){
			cin >> a;
			if(abs(last) % 2 != abs(a) % 2 || i == 1){
				sum = max(sum+a , a);
			}
			else{
				sum = a;
			}
			last = a;
			max_N = max(sum,max_N);
		}
		cout << max_N << endl;
	}

	return 0;
}