网站安全建设需求/今天刚刚的最新新闻
前缀和
n=int(input())
a=[0]+list(map(int,input().split()))
s=[0]*(n+1)
for i in range(1,n+1):s[i]=s[i-1]+a[i]前缀和与区间
前缀和与差分
提升修改效率
灵能传输
因为一次操作是对三个数进行，列如对a[i]进行操作，a[i-1]=a[i-1]+a[i]，a[i]=a[i]-2a[i]=-a[i]，a[i+1]=a[i+1]+a[i]，且三个数的和不变，联想到前缀和
a[i-1]=a[i-1]+a[i] → 现在的s[i-1]=s[i-2]+a[i-1]=s[i-2]+a[i-1]+a[i]=原来的s[i]
a[i]=a[i]-2a[i]=-a[i] → 现在的s[i]=s[i-1]+a[i]=s[i-1]-a[i]=s[i]-a[i]=原来的s[i-1]（因为上面s[i-1]变化位s[i]）
a[i+1]=a[i+1]+a[i] → 现在的s[i+1]=s[i]+a[i+1]=s[i]+a[i]+a[i+1]=s[i-1]+a[i]+a[i+1]=原来的s[i+1]（因为上面s[i]变化位s[i-1]）
问题转化为
t=int(input())
for i in range(t):n=int(input())a=[0]+list(map(int,input().split()))s=[0]*(n+1)for i in range(1,n+1):s[i]=s[i-1]+a[i]s.sort()ans=0for i in range(1,n+1):ans=max(ans,s[i]-s[i-1]) print(ans)如果s0和sn不是最小值和最大值，那该怎么做呢？
这时我们还可以先将s进行排序，也就是2，这时可以保证最大值最小；但因为s0和sn不能移动，所以，这时我们把s0和sn再放到起点和终点，
不过并不是简单的放两个点，而是将上图的1和3区域铺开，
铺开后，因为min→s0和sn→max与两头的s0→min和max→sn重复了，
根据贪心（来自2019蓝桥杯B组省赛 J.灵能传输_蓝桥杯灵能传输_紫色的～的博客-CSDN博客），重复路段取间隔点会使相邻点差值最小来看，就是一半跟着s0，sn取翻过来，一半保持不变，这个时候要注意s0→min和max→sn是从大到小排序，min→max是从小到大排序
操作完之后得到的排列所得出的结果必定是最大值最小的
t=int(input())
for i in range(t):n=int(input())a=[0]+list(map(int,input().split()))s=[0]*(n+1)for i in range(1,n+1):s[i]=s[i-1]+a[i]s0=0sn=s[n]if s0>sn:s0,sn=sn,s0s.sort()s0i=s.index(s0)sni=s.index(sn)b=[0]*(n+1)b[n]=s[n]vis=[1]*(n+1)L,R=0,nfor i in range(s0i,-1,-2):b[L]=s[i]vis[i]=0L+=1for i in range(sni,n+1,2):b[R]=s[i]vis[i]=0R-=1for i in range(n+1):if vis[i]:b[L]=s[i]L+=1ans=0for i in range(1,n+1):ans=max(ans,abs(b[i]-b[i-1]))print(ans)统计子矩阵
n,m,k=map(int,input().split())
a=[]
for i in range(n):l=list(map(int,input().split()))a.append(l)
s=[[0]*(m+1) for i in range(n+1)]
for i in range(1,n+1):for j in range(1,m+1):s[i][j]=s[i-1][j]+a[i-1][j-1]#列项求前缀和ans=0
for i1 in range(1,n+1):for i2 in range(i1,n+1):j1=1z=0for j2 in range(1,m+1):z+=s[i2][j2]-s[i1-1][j2]#先对矩阵的行上下限坐标为i2,i1-1的列进行左到右方向的累加，# 列的左限坐标j1不变，相当逐渐于扩大宽度while z>k:#如果右限坐标j2加到某一列时大于k时，进行尺取，直到z小于kz-=s[i2][j1]-s[i1-1][j1]j1+=1#j1向右移动ans+=j2-j1+1#说明j1 - j2 之间均满足小于k，数量为j2-(j1-1)
print(ans)