AcWing 4297. 截断数组(前缀和 双指针)
原题链接
中等
作者:
Mamba_Chu
,
2022-02-05 20:22:33
,
所有人可见
,
阅读 679
算法
双指针
C++ 代码
#include <iostream>
using namespace std;
const int N = 200010;
typedef long long LL;
LL a[N], s[N];
int main()
{
int n;
cin >> n;
for (int i = 1; i <= n; i ++ ) cin >> a[i];
//预处理前缀和
for (int i = 1; i <= n + 1; i ++ )
s[i] = s[i - 1] + a[i];
LL res = 0;
for (int i = 0, j = n + 1; i < j && i < n; ) //将两个指针分别指向0 和 n + 1的位置 因为存在s1 = s3 = 0
{
if (s[i] == (s[n + 1] - s[j - 1])) //判断s1 s3是否相等
{ //s1-->(a[0] ~ a[i]) s3-->(a[j] ~ a[n+1])
res = max(res, s[i]);
i ++, j -- ; //同时向中间移动
continue;
}
if (s[i] > (s[n + 1] - s[j - 1])) //左大右小 天平左边底 右边加砝码 即 j 左移
j -- ;
else if (s[i] < (s[n + 1] - s[j - 1])) //做小右大 左边加砝码 ~ ~
i ++;
}
cout << res << endl;
return 0;
}