Ez Python Solution - Modified Kadane's Algorithm


#1
class Solution:
    # @param A : string
    # @return a list of integers
    def flip(self, A):
        arr = [1 if i == '0' else -1 for i in A]
        
        max_so_far = float('-inf')
        curr_max = 0
        res = []
        start = 0
        
        for i in range(len(A)):
            curr_max += arr[i]
            
            if curr_max > max_so_far and curr_max >= 0:
                max_so_far = curr_max
                res = [start + 1, i + 1]
            if curr_max < 0:
                curr_max = 0
                start = i + 1
        
        return res