首页 > 试题广场 >

数组重乘法

[编程题]数组重乘法
  • 热度指数：98 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}一个包含 n 个整数的数组，你需要重新排列数组的元素，使得相邻两个元素的乘积之和最大。即最大化：(a'_1\times a'_2) + (a'_2 \times a'_3) + \cdots +( a'_{n-1}\times a'_n)。

输入描述:
\hspace{15pt}每个测试文件均包含多组测试数据。第一行输入一个整数 T\ (1\leqq T\leqq 10^5) 代表数据组数，每组测试数据描述如下：

\hspace{15pt}第一行包含一个整数 n\ (2 \leqq n \leqq 2 \times 10^5)，表示数组的长度。
\hspace{15pt}第二行 n 个整数表示数组的每个值 a_i\ (1 \leqq a_i \leqq 10^5)。

\hspace{15pt}除此之外，保证单个测试文件的 n 之和不超过 2 \times 10^5。


输出描述:
对于每组测试数据：
\hspace{15pt}在单独的一行输出一个整数，表示最大的 S 值。
示例1

输入

2
4
1 2 3 4
4
3 4 5 6

输出

23
69

说明

\hspace{15pt}对于第一组测试数据，我们重排为：\{2,4,3,1\} 最优，此时 S=2\times 4+4\times 3+3\times 1=23，最大。
算法知识视频讲解
添加回答

这道题你会答吗？花几分钟告诉大家答案吧！

提交观点

问题信息

难度：
0条回答 12浏览

热门推荐

相关试题

数组重乘法

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号