题目:
给定一个长度为n的,仅包含0,1的数列。例如1,0,0,1,1,1,0。我们可以轻易算出,它的最长全1区间长度是3。从数组的第4位到第6位。
现在,你获得了k次可以将某个位置上的0变为1的机会,但可以不用完所有的机会。
请你给出,你使用了你的变化机会后,这个数列的最长全1区间最大是多少 分析:
要使最大全1区间最长,一定是将某段连续区间内的0变为1。由此,可从左到右扫描整个数组,记录每个位置向右依次将0变为1后的最大全1区间长度。最后求整个数组的最大值。 上代码:
a = input().split()
b = input().split()
n, k = int(a[0]), int(b[0])
alist = [int(x) for x in b]
#n, k = 4, 1
#alist = [0, 1, 0, 1]
maxlen = []
end = 0 # 指向全1区间的结尾
start = 0 # 指向全1区间的开头
while end < n: # 结束条件:end扫到末尾
# 找到当前start对应的end的最远位置
while k >= 0 and end < n:
if alist[end] == 1: # 如果是1,继续走
end += 1
continue
k -= 1 # 如果是0,消耗一次0到1的变化机会
end += 1
maxlen.append(end - start) # 记录此时的最长全1区间
# start向前挪动一位
if alist[start] == 0: # 如果挪动前start是0,则可节省1次01变化
k = 1
start += 1
print(max(maxlen))