Самый большой подмассив с равным числом 0 и 1, логика c не работает в python

Question

Учитывая массив, содержащий только 0 и 1, найдите самый большой подмассив, который не содержит равных 0 и 1. Ожидаемая сложность по времени O (n).

Этот вопрос из - https://www.geeksforgeeks.org/largest-subarray-with-equal-number-of-0s-and-1s/

, что я сделал, я заменил 0 на -1 и нашел самый длинный подмассив с суммой 0.

код -

def maxLen(arr):
    n = len(arr)
    ht = {}
    end = -1
    max_len = 0
    cur_sum = 0
    for i in range(n):
        if arr[i]==0:
            arr[i] = -1

        cur_sum += arr[i]
        if cur_sum == 0:
            max_len = i+1
            end = i
        if ht.get((cur_sum+n)):    
            if max_len < (i-ht[(cur_sum+n)]):
                max_len = i-ht[(cur_sum+n)]
                end = i
        else:
            ht[(cur_sum+n)] = i

    return max_len

этот код не работает для тестового примера - maxLen([0, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1])

правильный вывод равен 28, а мой вывод равен 26

Но написание того же кода на с ++ работает нормально, не могу понять, почему не в python, где я ошибаюсь?

Answer 1

Ваш код просматривает только подмассивы, начиная с первого элемента - другими словами, вы смотрите только подмассив первого элемента, затем подмассив первых двух элементов, затем подмассив первых трех, и так далее. Самый большой подмассив с равным количеством 0 и 1 может начинаться со второго, третьего или четвертого элемента. Вот что происходит с вашим неудачным тестовым примером:

>>> bar
[-1, 1, 1, 1, -1, -1, 1, -1, 1, -1, 1, -1, 1, -1, -1, 1, 1, -1, -1, 1, -1, -1, -1, 1, 1, 1, -1, -1, 1]
>>> sum(bar[1:]) # sum from second element to the end
0

Отсутствует предоставленный вами код (который упоминается в ссылке GeeksforGeeks), это вложенный l oop, так что для каждого индекса в list, вы выполняете операцию суммирования от этого индекса до конца списка.