题解 | #小苯的麦克斯#(C++)
小苯的麦克斯
https://www.nowcoder.com/practice/de5b60b23a014f1bb66b8164faea3d0d
感觉有点诈骗的意味
假如区间是可以只取一个数的，那么显然最后求得ans = max - 0，不论max值是否为0
但题目要求我们的区间至少得取2个数，所以我们可以从上面这个思路进行一下延伸
可以证明按如下情况分类：
1.当max值两侧没有0的时候（如max在边缘则是一侧），ans = max
2.当max值两侧都有0的时候（如max在边缘则是一侧），ans = max - k
----k是由max值是不是1决定的，如果max值为1，那k = 2，否则为1
证明如下：
若最大值为1
那么如果旁边都是0，那得到ans = 1 - 2 = -1，如果旁边不全是0（即旁边有1），ans = 1 - 0 = 1
若最大值不为1
设次大值 = max - m(m >= 1)，那么由次大值得到的ans必然<= max - m（旁边不都是0） 并且 >= max - m - 1（旁边都是0），而由最大值max得到的ans必然<= max（旁边不都是0） 并且 >= max - 1（旁边都是0），由m >= 1，可以发现由最大值max得到的ans是始终大于等于由次大值得到的ans的
逻辑大概就是这样，看看代码会好理解一些可能（虽然感觉实现写的有点丑）
时间复杂度O(n)
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(x) cerr << #x << ": " << x << '\n';
// #define int long long
#define ctz __builtin_ctzll // 返回二进制表示中末尾连续0的个数
#define clz __builtin_clzll // 返回二进驻表示中先导0的个数
#define count1 __builtin_popcountll // 返回二进制表示中1的个数
// 上面仨不是ll的时候记得调整
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int hash_base = 881;
const int N = 1e6 + 10000;
const double EPS = 1e-8;
const ll MOD = 676767677;
// const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll INF = 0x3f3f3f3f3f3f3f3f;
ll dir[4][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}};
ll dirr[8][2] = {{1, 0}, {-1, 0}, {0, -1}, {0, 1}, {1, 1}, {1, -1}, {-1, -1}, {-1, 1}};
void LiangBaiKai()
{
}
void Aiden()
{
ll m, n, k, sum = 0, ans = 0, num = 0, mi = INF, ma = -INF, cnt = 0, x, y, z, len, t, l, r, cur;
string s1, s2;
cin >> n;
vector<ll> a(n);
ans = -INF;
for (ll i = 0; i < n;i++)
{
cin >> a[i];
if (a[i] >= ma) // a[i]是当前最大值，要去进行判断
{
ma = a[i];
bool flag = 1;
if (i == n - 1) // 特判a[i]处于头尾的状况
{
if (a[i - 1] == 0)
ans = max(ans,a[i] - (a[i] == 1 ? 2 : 1));
else
ans = max(ans, a[i]);
}
else if (i == 0)
{
if (a[i + 1] == 0)
ans = max(ans, a[i] - (a[i] == 1 ? 2 : 1));
else
ans = max(ans, a[i]);
}
else
{
if (a[i - 1] == 0 && a[i + 1] == 0)
ans = max(ans, a[i] - (a[i] == 1 ? 2 : 1)); // 旁边都是0，那么当前的答案 = a[i] - k，k是由a[i]值是不是1决定的，如果a[i]值为1，那k = 2，否则为1，和原本的答案取更大的那个
else
ans = max(ans, a[i]); // 旁边不全是0，当前答案就是a[i]，和原本答案取更大的那个
}
}
}
cout << ans << endl;
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
LiangBaiKai();
int _ = 1;
cin >> _;
while (_--)
Aiden();
return 0;
}
/*
@@@@@@
@@@@@@@@@@
@@@@@@@@@@@@@
@@@@@@@@@@@@@@@
@@@@@@@@@@@
@@@@
@
@@@@@@@@@@ @@ @@@@@@@@@@@@
@@@@@ @ @@@@@
@@@ @ @@@
@@@ @@ @@@
@@ @@@
@@ @@
@@ @@
@@ @@
@ @@
@ @@@@@@@@ @@
@ @@@ @@@@@@@@@ @
@@ @@@@@@@ @@@@@@@@ @@@@@@ @
@ @@@@@@@@@@@@@@@@@@@@@@@@@@ @@
@ @@@@@@@@@@@ @@@@@@@@@@@ @
@@@@@@@@@@@@@ @@@@@@@@@@@@@@ @ @@@@@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@@@@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@ @@@ @@@ @
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@
@@@@@@ @@@@@@@@@@ @@@@@@@@@@@@@@ @@
@@@@@ @@@@@@@ @@@@@@ @@ @@@@@@@@@@@ @@@
@@@@@ @@@@@@@@ @@@@ @@@@@@@ @@@@@@@@@@@ @@
@@@@@@ @@@@@@@ @@@@@ @@@@@@@ @@@@@@@@@@@@ @@@@@@@
@@@@@@@ @ @@@@@@ @@@@@@@ @@@@@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @ @ @@@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @ @@@@@ @ @@@@ @ @@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ @@ @@ @@ @@@ @@@@@ @@@@@@@@@@
@@@@@@@ @@@@@@@@@@@@@@ @@@@@@ @@@@@ @ @@@@@@@@
@@@@@@ @@@@@@@@@@@ @ @@@@@@@@
@@@@ @@@@@@@@ @@ @@@@@@@
@@ @@ @@@@@
@@@ @@
@@@ @@@
@@@@@@@@@@@@ @@@@@@@@@@@
@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
*/
