# Given a binary array, find the maximum number of consecutive 1s in this array if you can flip at most one 0.
#
# Example 1:
# Input: [1,0,1,1,0]
# Output: 4
# Explanation: Flip the first zero will get the the maximum number of consecutive 1s.
#     After flipping, the maximum number of consecutive 1s is 4.
# Note:
#
# The input array will only contain 0 and 1.
# The length of input array is a positive integer and will not exceed 10,000
# Follow up:
# What if the input numbers come in one by one as an infinite stream? In other words, you can't store all numbers
# coming from the stream as it's too large to hold in memory. Could you solve it efficiently?
#


class Solution(object):
    def findMaxConsecutiveOnes(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res, cur, cnt = 0, 0, 0
        for n in nums:
            cnt += 1
            if n == 0:
                cur = cnt
                cnt = 0

            res = max(res, cur + cnt)
        return res

    def findMaxConsecutiveOnes2(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        left, right, lastZero, res = -1, 0, -1, 0
        for n in nums:
            if not n:
                left = lastZero
                lastZero = right
            res = max(res, right - left)
            right += 1

        return res


if __name__ == '__main__':
    print Solution().findMaxConsecutiveOnes([1, 0, 1, 1, 0])
    print Solution().findMaxConsecutiveOnes2([1, 0, 1, 1, 0])
    print Solution().findMaxConsecutiveOnes2([])
    print Solution().findMaxConsecutiveOnes2([1])
