Python using two pass pre-process


  • 0

    dp1[i] stands for up to index i, how many continuous 1 appears
    dp2[i] stands for from index i on, how many continous 1 appears

    dp2 can be avoid if the second right to left pass can maintain what dp2 stores, but here I choose to be more consistant with the coding style.

    class Solution(object):
        def findMaxConsecutiveOnes(self, nums):
            dp1 = [0 for i in range(len(nums) + 2)]
            dp2 = [0 for i in range(len(nums) + 2)]
            cnt = 0
            for i in range(len(nums)):
                if nums[i] == 1:
                    cnt += 1
                else:
                    cnt = 0
                dp1[i] = cnt
            cnt = 0
            for i in range(len(nums) - 1, -1, -1):
                if nums[i] == 1:
                    cnt += 1
                else:
                    cnt = 0
                dp2[i] = cnt
            ans = 0
            for i in range(len(nums)):
                ans = max(ans, dp1[i - 1] + 1 + dp2[i + 1])
            return ans
    

Log in to reply
 

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