Выведение из списка области с наиболее часто повторяющимися единицами

Question

Дан список случайных чисел из нулей и единиц [а1, ..., аn]. Написать программу поиска наибольшей подпоследовательности, которая заполнена единицами. Вывести на экран индексы начала и конца найденного участка.

Пока что у меня есть только рандомный список из единиц и нулей:

import random
n=int(input("n="))
a=[]
for i in range(n):
    a.append(random.randint(0,1))
print("spisok: ", a)

Answer 1

алгоритм:

пройтись последовательно по всем элементам списка (позициям списка)
    если элемент равен 1, то добавить индекс во временный список
    если элемент равен 0, то
        если длина временного списка больше длины итогового списка - заменить итоговый список временным списком
        обнулить временный список

недостаток алгоритма в том, что приходится вести 2 новых списка в дополнении к имеющемуся, преимущество - короткий код

другой алгоритм:

пройтись последовательно по всем элементам списка (позициям списка)
    если элемент равен 1, то 
        если длина временной последовательности равна 0 то запомнить в качестве временной начальной позиции текущую позицию в списке
        увеличить длину временной последовательности на 1
    если элемент равен 0, то
        если длина временной последовательности больше длины итоговой последовательности, то
            записать вместо длины итоговой последовательности длину временной последовательности
            записать вместо начальной позиции итоговой последовательности начальную позицию временной последовательности
        обнулить длину временной последовательности
вывести индексы начиная с начальной позиции итоговой последовательности в кол-ве длины итоговой последовательности

преимущество алгоритма в том, что не надо использовать дополнительные списки

Answer 2

@Ghost, накидал на коленке. Есть одно но в этом алгоритме - если будет более 1 одинаковой длины, то запомнятся индексы последней комбинации. Но в условии ничего про это не сказано:

import random

a = []
count1 = 0
cash_dict = {}
cash_lst = []
for i in range(int(input("n="))):
    val = random.randint(0, 1)
    a.append(val)
    if val == 1:
        count1 += 1
        cash_lst.append(i)
    else:
        if count1 > 0:
            cash_dict[count1] = cash_lst
            cash_lst = []
            count1 = 0
print("spisok: ", a)
print("max_size1=", cash_dict[max(cash_dict.keys())])

Answer 3

Просто как вариант, возможно кому-то будет полезен или интересен.

Метод finditer ищет все последовательности единиц и возвращает начало и конец каждой последовательности. Функция map, используя соответствующий ключ, возвращает самую длинную последовательность. С помощью span получаем ее начало и конец:

from re import finditer
from random import choices

c = choices([0,1], k=30)
print(*c, sep='')
'''
100000100100111101000001100100
'''
s, e = max(finditer(r'1+', ''.join(map(str, c))), key=lambda m: m.end()-m.start()).span()
print(f'start:{s} end:{e-1}')
'''
start:12 end:15

БЛОГ НА HUSL

Выведение из списка области с наиболее часто повторяющимися единицами

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