Максимальная сумма из двух массивов, выбирающих один элемент из каждого так, что их индекс отличается на 3

Question

Я хочу повысить эффективность задачи (python) с O(n^2) до O(n). Проблема в том, что у меня есть два массива k=[11,11,13,11,12,15] и l=[7,5,10,9,5,9,11]. Я хочу найти max sum, выбирая один элемент из каждого массива, и индекс элементов из каждого массива должен отличаться на 3.

Для двух вышеупомянутых массивов это должно дать мне сумму 24. Решение грубой силы, которое я могу придумать, состоит в том, чтобы перебрать оба списка декартовым способом, что дает эффективность как O(n^2). Ниже мой код.

max=0
    for i in range(len(array_k)):
        for j in range(len(array_l)):
            if (array_k[i]+array_l[j])>max and abs(i-j)>=3:
                max=array_k[i]+array_l[j]


return   max

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

Answer 1

это должно дать мне сумму 24

На самом деле 25, но в любом случае я думаю, что получил N log N решение:

array_k = [11, 11, 13, 11, 12, 15]
array_l = [7, 5, 10, 9, 5, 9, 11]

new_k = [(pos, val, True) for pos, val in enumerate(array_k)]
new_l = [(pos, val, False) for pos, val in enumerate(array_l)]

r = new_k + new_l

r.sort(key=lambda el: el[1], reverse=True)

first_pos = r[0][0]
first_val = r[0][1]
first_type = r[0][2]

for i in range(1, len(r)):
    pos, value, type_ = r[i]
    if type_ is not first_type and abs(pos - first_pos) >= 3:
        print("MAX = ", first_val + value)
        break

Дайте мне знать, если вам нужны дальнейшие объяснения.