Блог

Учитывая массив целых чисел A размера N. Найдите самую длинную подпоследовательность A, которая является нечетно-четной.

Подпоследовательность считается нечетной-четной в следующих случаях:

Первый элемент подпоследовательности нечетный, второй элемент четный, третий элемент нечетный и так далее. Например: [5, 10, 5, 2, 1, 4], [1, 2, 3, 4, 5]

Первый элемент подпоследовательности четный, второй элемент нечетный, третий элемент четный и так далее. Например: [10, 5, 2, 1, 4, 7], [10, 1, 2, 3, 4]

Возвращает максимально возможную длину нечетно-четной подпоследовательности.

Примечание: Массив B является подпоследовательностью массива A, если B может быть получен из A путем удаления нескольких (возможно, нуля или всех) элементов.

Код приведен ниже

 def solve(A):
    n = len(A)
    sln =[]
    for i in range(n):
        for j in range(i):
            if A[i]%2 == 0:
                if A[j]%2==1 and A[j] < A[i]:
                    sln[i] = max(sln[i],sln[j] 1 )

            else:
                if A[j]%2==1 and A[j] < A[i]:
                    max(sln[i],sln[j] 1 )
    return sln
A = [1, 2, 2, 5, 6]
solve(A)
 

Я получаю ошибку индекса ----> sln[i] = max(sln[i],sln[j] 1 ) , Почему ошибка индекса приходит j каждый раз меньше, чем я

Вы присваиваете значение индексу списка, у которого еще нет значения:

     sln =[]
# ...
                    sln[i] = max(sln[i],sln[j] 1 )
 

Вы можете просто добавить к решению, когда вместо этого найдете новые совпадения.

Однако вот более простое решение в целом:

 def solve(a):
    if not a:
        return []
    sln = [a[0]]
    for x in a[1:]:
        if x % 2 != sln[-1] % 2:
            sln.append(x)
    return sln


example = [1, 2, 2, 5, 6]
print(solve(example))
 

Первый бит гарантирует отсутствие ошибок при передаче пустого списка. Решение всегда включает в себя первый элемент. Все остальные элементы будут включены, если их значение mod 2 отличается от последнего элемента в решении до сих пор.

Еще более простым решением (фактически однострочным), основанным на той же идее, было бы следующее, но его немного сложнее читать, поэтому лучше, если краткость сама по себе является целью:

 def solve_short(a):
    return [x for n, x in enumerate(a) if not n or x % 2 != a[n-1] % 2]
 

Я не измерял время, но я бы ожидал solve_short() , что буду бегать быстрее, чем solve() обычно, — если это имеет значение.

Обратите внимание, что в коротком решении используется тот факт, что для правильного решения может быть включено любое число, которое не имеет такой же четности, как его предшественник в исходном списке, даже если это не так явно, как логика в более длинном решении.

Мне было любопытно, и я провел тест — более длинное решение на самом деле работает лучше, чем короткое, но вот одно, которое работает лучше в большинстве случаев:

 def solve_fast(a):
    return [] if not a else [a[0]]   [x for x, y in zip(a[1:], a) if x % 2 != y % 2]
 

Еще два способа и ориентир:

 # inspired by Grismar
def solve(a):
    return [x for x, y in zip(a, [.5]   a) if (x   y) % 2]
 

 from itertools import groupby

def solve(a):
    return [next(g) for _, g in groupby(a, 1 .__and__)]
 

Контрольные сроки для a = random.choices(range(100), k=10**6) :

 124 ms  124 ms  128 ms  125 ms  127 ms  Grismar1
172 ms  228 ms  291 ms  178 ms  180 ms  Grismar2
102 ms  105 ms  106 ms  102 ms  106 ms  Grismar3
 96 ms   86 ms   89 ms   85 ms   85 ms  dont_talk1
162 ms  179 ms  165 ms  166 ms  165 ms  dont_talk2
 

Тестовый код (попробуйте его онлайн!):

 from random import choices
from timeit import repeat
from itertools import groupby

def Grismar1(a):
    if not a:
        return []
    sln = [a[0]]
    for x in a[1:]:
        if x % 2 != sln[-1] % 2:
            sln.append(x)
    return sln

def Grismar2(a):
    return [x for n, x in enumerate(a) if not n or x % 2 != a[n-1] % 2]

def Grismar3(a):
    return [] if not a else [a[0]]   [x for x, y in zip(a[1:], a) if x % 2 != y % 2]

def dont_talk1(a):
    return [x for x, y in zip(a, [.5]   a) if (x   y) % 2]

def dont_talk2(a):
    return [next(g) for _, g in groupby(a, 1 .__and__)]

solvers = Grismar1, Grismar2, Grismar3, dont_talk1, dont_talk2

# correctness (somewhat... only checks lengths)
for length in range(20):
    for _ in range(10):
        a = choices(range(100), k=length)
        expect = solvers[0](a[:])
        for solver in solvers:
            result = solver(a[:])
            assert len(result) == len(expect)

for _ in range(3):
    a = choices(range(100), k=10**6)
    for solver in solvers:
        copies = iter([a[:] for _ in range(5)])
        times = repeat(lambda: solver(next(copies)), number=1)
        print(*('= ms ' % (t * 1e3) for t in times), solver.__name__)
    print()