题解 | #丢手绢#

算法：双指针

时间复杂度：O(n)

思路：

以$ii$为右端点，$jj$为左端点；

$ii$向右走，一开始距离必为$i,ji,j$之间距离；

当$ii$走到某点时，距离变为$i,ji,j$之外距离，且$ii$再向前走只会是距离减小；

所以$ii$停止，$jj$开始走，使距离增大，此时距离为$i,ji,j$之外距离；

当$jj$走到某点时，距离又变为$i,ji,j$之间距离，$ii$继续走……

n=int(input())
a=[]
for i in range(n):
    a.append(int(input()))
s=sum(a)
j=0;ans=0;cnt=0
for i in range(n):
    cnt+=a[i]
    while j<=i and s-cnt<cnt:
        ans=max(ans,s-cnt)
        cnt-=a[j]
        j+=1
    ans=max(ans,cnt)
print(ans)