1

На вход подается массив из нулей и единиц. Необходимо реализовать функцию, которая возвращает длину максимальной подпоследовательности, в котором количество нулей и единиц совпадают. Пример последовательности: [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_
7
  • Реализуйте, кто ж Вам запрещает? 11 ноя 2020 в 12:14
  • Учебные задания допустимы в качестве вопросов только при условии, что вы пытались решить их самостоятельно перед тем, как задать вопрос. Пожалуйста, отредактируйте вопрос и укажите, что именно вызвало у вас трудности при решении задачи. Например, приведите код, который вы написали, пытаясь решить задачу 11 ноя 2020 в 12:15
  • Мне не нужна реализация, мне требуется подсказка алгоритма или направление в какую сторону думать, которую я не могу придумать пока. Вот и обратился на этот ресурс. 11 ноя 2020 в 12:25
  • Тогда измените вопрос. В таком виде его закроют, как учебное задание. 11 ноя 2020 в 12:47
  • Ваш подход очень даже правильный. Известно, какие тесты проваливает?
    – MBo
    11 ноя 2020 в 17:08

2 ответа 2

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

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

1
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_

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.