Haidora and suspicious formula (Editorial)

Solution

Claim. It's optimal to check only maximum three values from left and right after sorting

We only care about smallest three elements (when they're negative) and largest three elements (when they're positive) , the other elements are irrelevant to our $\max$ expression.

For n \le 6 , we can run brute-force directly with total of 6^3=216 iterations.

This is sufficient because we realize that if the two smallest elements are negative then there product is positive which may be larger than the product of largest two elements in some certain cases thus it's sufficient to check them.

Otherwise , we pick b_1=\{a_1,a_2,a_3\} for smallest values , and b_2=\{a_{n-2},a_{n-1},a_n\} which gives us \{a_1,a_2,a_3,a_{n-2},a_{n-1},a_n\} , we can run the brute force for the relevant values and we get 6^3=216 iterations as well.

This gives us a total maximum computation of N \log N+216 \times 1000 which is roughly 4 \cdot 10^6 which is good.

Complexity \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()