Python DP solution, O(n) time and O(1) space


  • 0
    H

    First, let T[i] represents the answer of the sub-problem where the flipped array of 1's must end with the ith digit.

    If nums[i] is 1, then we don't flip the bit, T[i] = T[i-1] +1.
    if nums[i] is 0, then we flip bit bit to 1, T[i] = number of continous 1's before ith digit +1. We could use another array C to hold the information, where C[i] is the number of continous 1's ending at digit i. So here T[i] = C[i-1] +1.

    C could be built easily along the iteration. C[i] = C[i-1] +1 if nums[i] is 1 else C[i] = 0. And the final answer would be max(T).

    Note that calculation at any step only depends on the C and T values of the previous step, so only two single values recording the information in the previous step will be enough. The code with O(1) space is here:

    class Solution(object):
        def findMaxConsecutiveOnes(self, nums):
            """
            :type nums: List[int]
            :rtype: int
            """
            maxL = 0  # maximum length
            cont_1 = 0 # the number of continous 1's so far. 
            end_L = 0  # answer with the current digit being the last digit
            
            for i in nums:
                if i==0:
                    end_L = cont_1+1
                    cont_1 = 0
                elif i==1:
                    end_L = end_L+1
                    cont_1 = cont_1 + 1
                maxL = max(maxL,end_L)
            
            return maxL
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.