Maximum Product
题意翻译
一共 $t$ 组数据。
给定 $n$ 个数、让你找 $5$ 个数,让它们的乘积最大。
每个数可正可负。
题目描述
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<j<k<l<t $ ).
输入输出格式
输入格式
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.
The first line of each test case contains a single integer $ n $ ( $ 5\le n\le 10^5 $ ) — the size of the array.
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.
It's guaranteed that the sum of $ n $ over all test cases does not exceed $ 2\cdot 10^5 $ .
输出格式
For each test case, print one integer — the answer to the problem.
输入输出样例
输入样例 #1
4
5
-1 -2 -3 -4 -5
6
-1 -2 -3 1 2 -1
6
-1 0 0 0 -1 -1
6
-9 -7 -5 -3 -2 1
输出样例 #1
-120
12
0
945
说明
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 $ .
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 $ .
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 $ .
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 $ .