# 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.
#
#
#
# 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]
# Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.
# 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]
# Bolded numbers were flipped from 0 to 1.  The longest subarray is underlined.
#
#
# Note:
#
# 1 <= A.length <= 20000
# 0 <= K <= A.length
# A[i] is 0 or 1

class Solution(object):
    # time complexity : O(N) N : len(A)
    # this is a sliding window issue
    # right keep moving, left move with him, although there is nested loop
    # but right and left would move together and keep a fixed distance
    # so it is still O(N)
    def longestOnes(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: int
        """
        res, zeros, left = 0, 0, 0
        # time : O(N)
        for right in xrange(len(A)):
            if A[right] == 0:
                zeros += 1

            while zeros > K:
                if A[left] == 0:
                    zeros -= 1
                left += 1

            res = max(res, right - left + 1)

        return res


if __name__ == '__main__':
    print Solution().longestOnes([1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], 2)
    print Solution().longestOnes([0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], 3)
