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

Условие:

Пусть S — последовательность из N целых чисел, пронумерованных подряд начиная с 1. Обозначим S(L, R) подпоследовательность, состоящую из идущих подряд элементов, входящих в S, начиная с элемента с номером L и заканчивая элементом с номером R. Требуется найти такие значения номеров элементов L и R, где 0 < L< R ≤ N, чтобы сумма элементов подпоследовательности S(L, R) была нечётной и отрицательной.

В ответе укажите длину подобной подпоследовательности (то есть количество элементов, входящих в эту подпоследовательность). Если таких подпоследовательностей несколько — укажите максимальную длину из них.

Входные данные
Дано два входных файла (файл А(~1000 чисел) и файл В(~300 000 чисел)), каждый из которых в первой строке содержит число N (3 < N < 10 000 000) - количество целых чисел. Каждая из следующих М строк содержит одно целое число, значение которого по модулю не превышает 1000.

В ответе укажите два числа: сначала значение искомой величины для файла А, затем — для файла В.

Типовой пример организации данных во входном файле

8
-73
153
35
0
-44
78
-69
2

При таких входных данных условию задачи удовлетворяет сумма 0 + (-44) + 78 + (-69) и 0 + (-44) + 78 + (-69) + 2. Ответом на вопрос задачи является число 5.

К задаче есть 2 файла: на и на 300 000 чисел.

Моё решение:

Для первого файла подходит переборный алгоритм О(N^2). Для второго он не подходил, поэтому я попытался создать другой.

Идея была в том, чтобы создать массив сумм всех элементов от первого до i-того элемента и 2 массива предыдущих сумм для чётных и нечётных значений, каждая из которой была бы больше предыдущей. А потом проверять разность элементов первого массива и другого с иной чётностью. Если эта разность меньше 0, то переходить для следующей суммы.

Проблема в том, что после 30 000 элемента скорость сильно замедляется и выполнение для второго файла занимает несколько часов. Может ли кто-нибудь подсказать более оптимальный метод решения?

Мой код

f = open('file.txt')
n = int(f.readline())
a = [int(f.readline())]
sums = [a[0]]
for i in f:
    i = int(i)
    a.append(i)
    sums.append(sums[-1]+i)
mxs0 = [[], []]
mxs1 = [[], []]
k0 = []
k1 = []

for i in range(2,n):
    if sums[i-2] % 2 == 0:
        if len(k0) == 0:
            k0.append(i-2)
        elif k0[-1] < sums[i-2]:
            k0.append(i-2)
    if sums[i-2] % 2 == 1:
        if len(k1) == 0:
            k1.append(i-2)
        elif k1[-1] < sums[i-2]:
            k1.append(i-2)
    mxs0.append(k0)
    mxs1.append(k1)

lens = []
for i in range(2,n):
    print(i)
    if sums[i]%2==0:
        if len(mxs1[i]) > 0 > sums[i]-sums[mxs1[i][-1]]:
            for j in range(len(mxs1[i])):
                if sums[i]-sums[mxs1[i][j]] < 0:
                    lens.append(a[mxs1[i][j] + 1:i + 1])
                    break
    else:
        if sums[i] < 0:
            lens.append(a[0:i+1])
        else:
            if len(mxs0[i]) > 0 > sums[i]-sums[mxs0[i][-1]]:
                for j in range(len(mxs0[i])):
                    if sums[i]-sums[mxs0[i][j]] < 0:
                        lens.append(a[mxs0[i][j] + 1:i + 1])
                        break
cc = 0
lens = [i for i in lens if type(i) != int]
for i in range(len(lens)):
    cc = max(cc, len(lens[i]))
print(cc)