【每日一题】—— C. Yarik and Array（Codeforces Round 909 (Div. 3)）（贪心）

🌏博客主页：PH_modest的博客主页
🚩当前专栏：每日一题
💌其他专栏：
🔴 每日反刍
🟡 C++跬步积累
🟢 C语言跬步积累
🌈座右铭：广积粮，缓称王！

一.题目描述

题目大意：

子数组是数组的连续部分。
Yarik 最近发现了一个由 $n$ 个元素组成的数组 $a$ ，于是他对寻找一个非空子数组的最大和非常感兴趣。然而，Yarik 不喜欢奇偶校验相同的连续整数，因此他选择的子数组必须有相邻元素的交替奇偶校验。
例如， $[1,2,3]$ 可以接受，但 $[1,2,4]$ 不行，因为 $2$ 和 $4$ 都是偶数且相邻。
你需要帮助 Yarik 找出这样一个子数组的最大和。

题目链接：

C. Yarik and Array（Codeforces Round 909 (Div. 3)）

二.思路分析

这题就是贪心求解子序列最大和的题目，只不过多了一点限制条件；

1. 定义一个maxx先求取当前数组中的最大值
2. 定义一个sum求取当前子序列的和
3. 当sum<0的时候需要重新计算和，因为负数加上一个数只会越来越小；同时如果相邻的两数同为奇数或者同为偶数也是不满足条件的（abs(s[i]%2) == abs(s[i-1]%2)），也需要重新计算。需要注意的是元素可能为负数，所以取模的时候需要求取绝对值
4. 然后将maxx和sum进行比较，求取较大的值放入maxx

三.代码展示

//https://codeforces.com/contest/1899/problem/C
//首先需要判断奇偶，然后用sum存储当前序列的和，如果sum<0就重新计算（因为加上只会更小），求完和之后和之前的值进行比较，取最大的值
//
#include
#include
#include
#include
#include
#include
#include
#define int long long
using namespace std;

int s[200020];

void solve()
{
    int n;
    cin>>n;
    int maxx=-1e9;
    for(int i=0;i<n;i++)
    {
    	cin>>s[i];
    	maxx=max(maxx,s[i]);
	}
	int sum=s[0];
	for(int i=1;i<n;i++)
	{
		if(sum<0||abs(s[i]%2)==abs(s[i-1]%2))
		{
			sum=s[i];
		}
		else
		{
			sum+=s[i];
		}
		maxx=max(maxx,sum);
	}
	cout<<maxx<<"\n";
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int t;
	cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

最后：

每日一题系列旨在养成刷题的习惯，所以对代码的解释并不会特别详细，但足够引导大家写出来，选的题目都不会特别难，但也不是特别简单，比较考验大家的基础和应用能力，我希望能够将这个系列一直写下去，也希望大家能够和我一起坚持每天写代码。

之后每个星期都会不定期更新codeforces和atcoder上的题目，想要学习算法的友友们千万别错过了，有什么疑问欢迎大家在评论区留言或者私信博主！

在这里送大家一句话：广积粮，缓称王！