Функция возвращающая длину максимального подмассива с условием

Question

На вход подается массив из нулей и единиц. Необходимо реализовать функцию, которая возвращает длину максимальной подпоследовательности, в котором количество нулей и единиц совпадают. Пример последовательности: [0, 0, 1, 0, 1, 1, 1, 0, 0, 0] В срезе массив с 1 (индексация с 0) по 8 количество нулей равно количеству единиц, длина подмассива - 8. Ниже моя реализация кода, но она не проходит тесты полностью. Нужна подсказка в чем именно ошибка

def longest_subsequence(arr):
    hash_table = {0:-1}
    k = 0
    max_ = 0
    temp = ...
    for idx, el in enumerate(arr):
        if el == 0:
            k += 1
        else:
            k -= 1

        if k not in hash_table:
            hash_table[k] = idx

        if k in hash_table:
            temp = idx - hash_table[k]

        if temp > max_:
            max_ = temp

    
    return max_

Answer 1

max=0
lt= [0,0,1,0,1,1,1,0,0,0,0,1,1,0,1,0,0,0,1,1,0,0,1]
for i in range(len(lt)):
    for j in range(i+1,len(lt)):
        if lt[i:j].count(0)==lt[i:j].count(1):
            if lt[i:j].count(0)>max:
                i_m=i
                j_m=j
                max=lt[i:j].count(0)
print(i_m,j_m,max)

Результат:

2 20 9

На вашем примере lt= [0, 0, 1, 0, 1, 1, 1, 0, 0, 0]

результат

0 8 4

В качестве домашнего задания предлагаю подумать, можно-ли и как этот скриптик оптимизироват.

Answer 2

def longest_subsequence(arr):
    hash_table = {0:-1}
    k = 0
    max_ = 0
    temp = ...
    for idx, el in enumerate(arr):
        if el == 0:
            k += 1
        else:
            k -= 1

        if k not in hash_table:
            hash_table[k] = idx

        if k in hash_table:
            temp = idx - hash_table[k]

        if temp > max_:
            max_ = temp

    
    return max_

БЛОГ НА HUSL

Функция возвращающая длину максимального подмассива с условием

Ответы (2 шт):