Максимальное количество элементов общего подмассива с одинаковой суммой
Нужно реализовать функцию возвращающую количество самого длинного подмассива двух массивов с одинаковой суммой. Пример:
arr_1 = [1, 2, 3, 2, 1]
arr_2 = [3, 2, 1, 5, 6]
# Функция должна вернуть 3 так как 1 + 2 + 3 == 3 + 2 + 1
arr_3 = [1, 2, 3, 4, 5]
arr_4 = [4, 5]
# Функция должна вернуть 2, так как 4 + 5 == 4 + 5
Функция, которая решает данную проблему и нуждается в оптимизации - уменьшении сложности алгоритма:
def total_subarray(string1, string2):
rows = [[0 for _ in string1] for _ in range(2)]
tmp_row = [0 for _ in string1]
result = 0
for i in range(len(string2)):
for j in range(len(string1)):
if string2[i] == string1[j]:
rows[1][j] = 1
if j:
rows[1][j] = rows[0][j-1] + 1
if rows[1][j] > result:
result = rows[1][j]
rows[0] = rows[1]
rows[1] = tmp_row[:]
return result
Прошу подсказки, в какую сторону думать, полагаю что нужно использовать алгоритм Кадана (префиксные суммы).