Код не проходит лимит по времени (оптимизация на python)

Рейтинг: 0Ответов: 1Опубликовано: 12.07.2023

Я решала задачу:

Вам даны n целых чисел a1, a2, …, an.

Найдите максимальное значение max(al, al+1, …, ar)·min(al, al+1, …, ar) по всем парам (l, r) целых чисел, для которых 1 ≤ l < r ≤ n.

Входные данные

Первая строка содержит одно целое число t (1 ≤ t ≤ 10000) — количество наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число n (2 ≤ n ≤ 105).

Вторая строка каждого набора входных данных содержит n целых чисел a1, a2, …, an (1 ≤ ai ≤ 106).

Гарантируется, что сумма n по всем наборам входных данных не превышает 3·105.

Выходные данные

Для каждого набора входных данных выведите одно целое число — максимально возможное значение произведения из условия.

Пример

входные данные

4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328

выходные данные

12
6
4761
381274500335

Написала по ней код:

n=int(input()) 
for x in range(n):
    m=int(input()) 
    a=list(map(int, input().split())) 
    ans=a[0]*a[1] 
    for l in range(m-1):
        for r in range(l+1, m):
            s=a[l:r+1] 
            if min(s)*max(s)>ans:
                ans=min(s)*max(s)
    print(ans)

Но он не проходит лимит по времени, подскажите пожалуйста, как его можно ускорить!!!

python
Источник: Stack Overflow на русском

Ответы

▲ 3Принят

Рассмотрим произведение на отрезке (l, r):

    *
  *           *
*       *
      *     *
          *
---------------
l . m . . . . r

Пусть m - позиция максимума в этом отрезке. Рассмотрим отрезок (m, m + 1) если m < r и (m - 1, m) иначе. Для определённости пусть будет (m, m + 1).

Максимумы у (l, r) и (m, m + 1) одинаковы. Минимум у (m, m + 1) больше или равен минимуму (l, r). Следовательно и произведение для (m, m + 1) не меньше произведения (l, r).

То есть для любого длинного отрезка (l, r) предъявлен короткий отрезок (m, m + 1) с таким же или большим произведением. Рассматривать длинные отрезки не надо, максимальное произведение получится на отрезке длины два.

Таких отрезков линейное количество, значит и сложность программы тоже будет линейная. Сейчас сложность вашей программы кубическая. Для n = 105 ваша программа сделает порядка 1015 операций. Линейная программа сделает порядка 105. Ускорение в 1010 раз.

for _ in range(int(input())):
    input() # skip n
    a = tuple(map(int, input().split())) 
    print(max(max(al, ar) * min(al, ar) for al, ar in zip(a, a[1:])))

$ cat input.txt
4
3
2 4 3
4
3 2 3 1
2
69 69
6
719313 273225 402638 473783 804745 323328

$ python max-min.py < input.txt
12
6
4761
381274500335