今天给大家讲最大乘积这道题目
最大乘积
内存限制：256 MiB
时间限制：1000 ms
输入文件：maximum.in
输出文件：maximum.out
题目类型：传统
评测方式：文本比较
题目描述
给你 n n n个整数 a 1 , a 2 , a 3 , a 4... a n a1,a2,a3,a4...an a1,a2,a3,a4...an 从中任意挑选出个数字，使得乘积最大，输出乘积最大值。
输入格式
输入有多组测试数据。
第一行为整数 t t t，表示测试数据组数。
每组测试数据第一行为整数 n n n，表示数字的数量。
每组测试数据第二行有 n n n个整数 a 1 , a 2 , . . . . a n a1,a2,....an a1,a2,....an
输出格式
每组测试数据输出只有个整数，表示挑选出个数字的乘积最大值。
样例
样例输入
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
样例输出
-120
12
0
945
思路
这个题目其实不难。我们先分析一下这个题目。
这个题目要我们从一组数据中 选取五个数 使得这五个数乘积最大。
简单一想 这个不很简单 我们直接从中选取五个最大的数字 然后将这五个数的成乘积直接输出不就完了吗。 但是 仔细一想又发现 不对。刚刚只局限于正数的情况 可是这里还有负数呢! 所以 我们要对这选出来的五个数分情况讨论。
我们要让乘积最大 那么选出来的五个数的乘积 都尽量应该是正数 所以 我们如果要选择负数 那么也最好让它成双成对的出现 因为负负得正 并且这个负数越小乘积就越大。根据此推断 我们将这五个数分为以下几种情况。
一：0个负数 5个正数。即选出这个数列里最大的五个数。
二：2个负数 3个正数。即选出这个数列里最大的三个数和最小的两个数。
三：4个负数 1个正数。即选出这个数列里最大的一个数和最小的四个数。
然后我们将这三种情况算出来的乘积取一个最大值即可。
但是这样就完了吗？ 不你想多了。因为如果这 n n n个数全是负数怎么办？
很简单 我们为了让乘积最大 我们将会选取最大的五个负数。但当我们再回头看一下 发现这不就是第一种情况吗？
所以 我们就不需要特判这种情况了。
代码
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include<bits/stdc++.h>
using namespace std;
long long a[100005];
int n;
int t;
int main()
{
freopen("maximum.in","r",stdin);
freopen("maximum.out","w",stdout);
//文件名输入输出
cin>>t;
while(t--)
{
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
//输入
sort(a+1,a+n+1);// 给这个数组排序
cout<<max(a[n]*a[n-1]*a[n-2]*a[n-3]*a[n-4],max(a[n]*a[n-1]*a[n-2]*a[1]*a[2],a[n]*a[1]*a[2]*a[3]*a[4]))<<endl;//按照思路中所讲的三种情况进行取最大值 并记得换行
}
return 0;//返回 0
}
|
总结
本篇文章就到这里了，希望能给你带来帮助，也希望您能够多多关注服务器之家的更多内容！
原文链接：https://blog.csdn.net/Minecraftwzy/article/details/118672941