P9367 [ICPC 2022 Xi'an R] Strange Sum

题意简述

给定长度为 $n$ 的序列 $a_i$，选择若干元素（可以不选），求元素之和的最大值。需要满足若选择 $a_i$，则所有长度为 $i$ 的子区间中最多只能选择 $2$ 个元素。

解题思路

假设选择编号最大的元素为 $a_x$，那么在区间 $[1,x]$ 中最多只能选择两个元素，因为序列中没有比 $a_x$ 编号更大的元素。

因此，整个序列中最多只能选择两个元素，考虑三种情况的最大值即可：

1. 不选择任何元素：$0$；
2. 选择 $1$ 个元素：$\max_1$；
3. 选择 $2$ 个元素：$\max_1+\max_2$。

参考代码

#include <bits/stdc++.h>
using namespace std;

const int inf=0x3f3f3f3f;
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int n;
	cin>>n;
	int mx1=-inf,mx2=-inf;
	for(int i=1;i<=n;i++)
	{
		int t;
		cin>>t;
		if(t>mx1){mx2=mx1;mx1=t;}
		else if(t>mx2){mx2=t;}
	}
	cout<<max({0,mx1,mx1+mx2})<<'\n';
	return 0;
}