Максимальное количество элементов общего подмассива с одинаковой суммой

Нужно реализовать функцию возвращающую количество самого длинного подмассива двух массивов с одинаковой суммой. Пример:

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

Прошу подсказки, в какую сторону думать, полагаю что нужно использовать алгоритм Кадана (префиксные суммы).


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