Условие:
Пусть 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)