P1396 - 乘积最大 - 优加优智OJ系统

内存限制：128 MB 时间限制：1.000 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：1 通过：1

输入 n 个正整数，第 i 个数为 ai。先将这 n 个数分成 3 组，分别求出每组数的和，然后再把求出的这 3 个和相乘。由于分组的方案有很多，最后乘积的值也各不相同，请你求出所有分组方案中乘积的最大值。

比如有 6 个数，分别为 1 2 3 1 2 3，第一种分法为{1，3}，{1，3}和{2，2}，这三组数的和的乘积为 64；第二种分法为{3}，{1，2，3}和{1，2}，这三组数的和的乘积为54；第三种…… 经验证，所有分法的乘积的最大值是 64。

第一行，一个正整数 n，表示一共有 n 个正整数。

第二行，n 个正整数，用一个空格分隔，第 i 个数为 ai。

一个正整数，表示所有分法的乘积的最大值。

6
1 2 3 1 2 3

数据规模：

对于 30%的数据，3 ≤ n ≤ 15，1 ≤ ai ≤ 15。

对于 60%的数据，3 ≤ n ≤ 25，1 ≤ ai ≤ 25。

对于 100%的数据，3 ≤ n ≤ 50，1 ≤ ai ≤ 50。

奥数

1396: 乘积最大