Haidora və şübhəli formula#12281

Haidora və şübhəli formula (Həll təhlili)

Problem Müəllifi:	Haidara Al Makdid
Hazırlayan:	Haidara Al Makdid
Redaktə edən:	Hasan Saleh (MathModel)

Həll

İddia. Sıralandıqdan sonra yalnız maksimum üç dəyəri soldan və sağdan yoxlamaq optimaldır.

Biz yalnız ən kiçik üç elementi (müsbət olmadıqda) və ən böyük üç elementi (müsbət olduqda) maraqlandırırıq, digər elementlər bizim $max$ ifadəmiz üçün əhəmiyyətsizdir.

$n \leq 6$ n \le 6 olduqda, birbaşa 6^3=216 iterasiya ilə brute-force işləyə bilərik.

Bu kifayətdir, çünki iki ən kiçik element mənfidirsə, onların hasilatı müsbət olur ki, bu da bəzi hallarda ən böyük iki elementin hasilatından daha böyük ola bilər, buna görə də onları yoxlamaq kifayətdir.

Əks halda, biz $b_{1} = {a_{1}, a_{2}, a_{3}}$ b_1=\{a_1,a_2,a_3\} ən kiçik dəyərlər üçün, və $b_{2} = {a_{n - 2}, a_{n - 1}, a_{n}}$ b_2=\{a_{n-2},a_{n-1},a_n\} seçirik ki, bu da bizə ${a_{1}, a_{2}, a_{3}, a_{n - 2}, a_{n - 1}, a_{n}}$ \{a_1,a_2,a_3,a_{n-2},a_{n-1},a_n\} verir, müvafiq dəyərlər üçün brute-force işlədə bilərik və biz də $6^{3} = 216$ 6^3=216 iterasiya alırıq.

Bu, $N lo g N + 216 \times 1000$ N \log N + 216 \times 1000 maksimum hesablamasına gətirib çıxarır ki, bu da təxminən $4 \cdot 1 0^{6}$ 4 \cdot 10^6-dır ki, bu da yaxşıdır.

Komplekslik $O (n lo g n + 216 \cdot t)$ \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()

Python