Гайдо́ра та підозріла формула (Розбір)

Рішення

Твердження. Оптимально перевіряти лише максимальні три значення зліва та справа після сортування.

Нам важливі лише три найменші елементи (коли вони негативні) та три найбільші елементи (коли вони позитивні), інші елементи не мають значення для нашого $\max$ виразу.

Для n \le 6 ми можемо безпосередньо виконати грубий перебір з загальною кількістю 6^3=216 ітерацій.

Цього достатньо, оскільки ми усвідомлюємо, що якщо два найменші елементи негативні, то їх добуток позитивний, що може бути більшим за добуток найбільших двох елементів у певних випадках, тому достатньо перевірити їх.

В іншому випадку, ми вибираємо b_1=\{a_1,a_2,a_3\} для найменших значень, і b_2=\{a_{n-2},a_{n-1},a_n\}, що дає нам \{a_1,a_2,a_3,a_{n-2},a_{n-1},a_n\}, ми можемо виконати грубий перебір для релевантних значень, і ми отримаємо 6^3=216 ітерацій також.

Це дає нам загальну максимальну обчислювальну складність N \log N + 216 \times 1000, що приблизно дорівнює 4 \cdot 10^6, що є добре.

Складність \mathcal{O}(n \log n + 216 \cdot t).

from math import *
def solve():
    n=int(input())
    a=list(map(int,input().split()))
    ans=-10**18
    if(n<=6):
        for i in range(n):
            for j in range(n):
                for k in range(n):
                    if(len({i,j,k})==3):
                        ans=max(ans,a[i]*a[j]+a[k])
    else:
        a.sort()
        v=[a[0],a[1],a[2],a[-1],a[-2],a[-3]]
        for i in range(6):
            for j in range(6):
                for k in range(6):
                    if(len({i,j,k})==3):
                        ans=max(ans,v[i]*v[j]+v[k])
    print(ans)
    
for _ in range(int(input())):
    solve()