AcWing 3493. 最大的和-滑动窗口python3
原题链接
简单
作者:
张麻子
,
2021-05-11 20:00:01
,
所有人可见
,
阅读 330
(滑动窗口) $O(n)$
python3 代码
#滑动指针
#优势就是不用开数组记录前缀和
n,k = map(int, input().split())
arr = list(map(int, input().split()))
bos = list(map(int, input().split())) #1 or 0
ans = 0
for a,b in zip(arr,bos):
ans+=a*b
delta = 0
for i in range(k):
delta += arr[i]*(1-bos[i])
delta_res = delta
l,r = 0, k
while r<n:
inc = arr[r]*(1-bos[r]) - arr[l]*(1-bos[l])
delta+=inc
l+=1
r+=1
if inc>0:
delta_res = max(delta_res, delta)
print(delta_res+ans)
nice, 又一个思路