# 1004. Max Consecutive Ones III

## Problem Setting¶

Given an array A of 0s and 1s, we may change up to K values from 0 to 1.

Return the length of the longest (contiguous) subarray that contains only 1s.

Variable Type Description
A list an array of 0s and 1s e.g., 111000
K int the maximum number of changes fliping from 0 to 1

### Example 1¶

Input: A = [1,1,1,0,0,0,1,1,1,1,0], K = 2

Output: 6

Explanation: [1,1,1,0,0,1*,1,1,1,1,1*]

Numbers with * (astarisk) were flipped from 0 to 1. The longest subarray is indicated as a line of bold numers.

### Example 2¶

Input: A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3

Output: 10

Explanation: [0,0,1,1,1*,1*,1,1,1,1*,1,1,0,0,0,1,1,1,1]

Numbers with * (astarisk) were flipped from 0 to 1. The longest subarray is indicated as a line of bold numers.

Note:

1 <= A.length <= 20000

0 <= K <= A.length

A[i] is 0 or 1

## Solution from abhi1027-%3A-Python-Sliding-window)¶

In [1]:
class Solution(object):
def longestOnes(self, A, K):
i=0;n=len(A);j=0
countk=K;res=float('-inf')
while j<n and i<n:
if A[j]==1:
pass
else:
if countk>0:
countk-=1
else:
while countk<0 or A[i]==1:
if A[i]==0:
countk+=1
i+=1
i+=1
res=max(res,j-i+1)
j+=1
return res

In [2]:
# Example 1
A = [1,1,1,0,0,0,1,1,1,1,0]
K = 2
s = Solution()
s.longestOnes(A, K)

Out[2]:
6
In [3]:
# Example 2
A = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1]
K = 3
s = Solution()
s.longestOnes(A, K)

Out[3]:
10

## Step-by-step understanding¶

1. Initialization
Variable Description
i the first counter to keep the pointer for the beggining of consecutive subarray of 1s
j the first counter to keep the pointer for the end of consecutive subarray of 1s
n the length of a given array A
countK the reverse counter to count down the number of flip
res the result integer starting from negative infinity
1. the first while loop

• i is set as a starting point

• j(end) is increased until the length of array or using the maximum number of changes
• if j is 1 then, skip to next
• if j is 0 then, subtract the number from countK

Continue the above loop till countK becomes 0

1. When the countK becomse 0, reset the process and move the position of i forward +1
• if the next position is 0 then revert the countK and add +1
• if the next position is 1 then simply move the index of i forward +1 without changing countK
In [4]:
A = [1,1,1,0,0,0,1,1,1,1,0]
K = 2
i=0;n=len(A);j=0
countk=K;res=float('-inf')
while j<n and i<n:
print('While loop start')
if A[j]==1:
pass
else:
if countk>0:
countk-=1
else:
print('Running out countK')
while countk<0 or A[i]==1:
print('Revert the countK for the number of 1')
if A[i]==0:
countk+=1

print('Move i position forward')
i+=1
print('Move i position forward')
i+=1
print('Found the consecutive sequence %i' % int(j-i+1))
print('Leave the max value between %.f and %i => leave %.f' % (res, int(j-i+1), max(res,j-i+1)))
res=max(res,j-i+1)
j+=1
print()

print('='*40)
print('All exploration is finished')
print('Final result is %.f' % res)

While loop start
Found the consecutive sequence 1
Leave the max value between -inf and 1 => leave 1

While loop start
Found the consecutive sequence 2
Leave the max value between 1 and 2 => leave 2

While loop start
Found the consecutive sequence 3
Leave the max value between 2 and 3 => leave 3

While loop start
Found the consecutive sequence 4
Leave the max value between 3 and 4 => leave 4

While loop start
Found the consecutive sequence 5
Leave the max value between 4 and 5 => leave 5

While loop start
Running out countK
Revert the countK for the number of 1
Move i position forward
Revert the countK for the number of 1
Move i position forward
Revert the countK for the number of 1
Move i position forward
Move i position forward
Found the consecutive sequence 2
Leave the max value between 5 and 2 => leave 5

While loop start
Found the consecutive sequence 3
Leave the max value between 5 and 3 => leave 5

While loop start
Found the consecutive sequence 4
Leave the max value between 5 and 4 => leave 5

While loop start
Found the consecutive sequence 5
Leave the max value between 5 and 5 => leave 5

While loop start
Found the consecutive sequence 6
Leave the max value between 5 and 6 => leave 6

While loop start
Running out countK
Move i position forward
Found the consecutive sequence 6
Leave the max value between 6 and 6 => leave 6

========================================
All exploration is finished
Final result is 6
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}