1406B.md (1607B)
1 Source: https://codeforces.com/problemset/problem/1406/B 2 3 B. Maximum Product 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 512 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given an array of integers $a_1,a_2,\ldots,a_n$. Find the maximum possible value of $a_ia_ja_ka_la_t$ among all five indices $(i, j, k, l, t)$ ($i \lt j \lt k \lt l \lt t$). 22 23 Input 24 25 The input consists of multiple test cases. The first line contains an integer $t$ ($1\le t\le 2 \cdot 10^4$) — the number of test cases. The description of the test cases follows. 26 27 The first line of each test case contains a single integer $n$ ($5\le n\le 10^5$) — the size of the array. 28 29 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($-3\times 10^3\le a_i\le 3\times 10^3$) — given array. 30 31 It's guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 32 33 Output 34 35 For each test case, print one integer — the answer to the problem. 36 37 Example 38 39 Input 40 41 ``` 42 4 43 5 44 -1 -2 -3 -4 -5 45 6 46 -1 -2 -3 1 2 -1 47 6 48 -1 0 0 0 -1 -1 49 6 50 -9 -7 -5 -3 -2 1 51 ``` 52 53 Output 54 55 ``` 56 -120 57 12 58 0 59 945 60 ``` 61 62 Note 63 64 In the first test case, choosing $a_1,a_2,a_3,a_4,a_5$ is a best choice: $(-1)\cdot (-2) \cdot (-3)\cdot (-4)\cdot (-5)=-120$. 65 66 In the second test case, choosing $a_1,a_2,a_3,a_5,a_6$ is a best choice: $(-1)\cdot (-2) \cdot (-3)\cdot 2\cdot (-1)=12$. 67 68 In the third test case, choosing $a_1,a_2,a_3,a_4,a_5$ is a best choice: $(-1)\cdot 0\cdot 0\cdot 0\cdot (-1)=0$. 69 70 In the fourth test case, choosing $a_1,a_2,a_3,a_4,a_6$ is a best choice: $(-9)\cdot (-7) \cdot (-5)\cdot (-3)\cdot 1=945$.