今天給大家講最大乘積這道題目

最大乘積

內(nèi)存限制：256 MiB

時(shí)間限制：1000 ms

輸入文件：maximum.in

輸出文件：maximum.out

題目類型：傳統(tǒng)

評(píng)測(cè)方式：文本比較　　

題目描述

給你 n n n個(gè)整數(shù) a 1 , a 2 , a 3 , a 4... a n a1,a2,a3,a4...an a1,a2,a3,a4...an 從中任意挑選出個(gè)數(shù)字，使得乘積最大，輸出乘積最大值。

輸入格式

輸入有多組測(cè)試數(shù)據(jù)。

第一行為整數(shù) t t t，表示測(cè)試數(shù)據(jù)組數(shù)。

每組測(cè)試數(shù)據(jù)第一行為整數(shù) n n n，表示數(shù)字的數(shù)量。

每組測(cè)試數(shù)據(jù)第二行有 n n n個(gè)整數(shù) a 1 , a 2 , . . . . a n a1,a2,....an a1,a2,....an

輸出格式

每組測(cè)試數(shù)據(jù)輸出只有個(gè)整數(shù)，表示挑選出個(gè)數(shù)字的乘積最大值。

樣例

樣例輸入

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

思路

這個(gè)題目其實(shí)不難。我們先分析一下這個(gè)題目。

這個(gè)題目要我們從一組數(shù)據(jù)中 選取五個(gè)數(shù) 使得這五個(gè)數(shù)乘積最大。

簡(jiǎn)單一想 這個(gè)不很簡(jiǎn)單 我們直接從中選取五個(gè)最大的數(shù)字 然后將這五個(gè)數(shù)的成乘積直接輸出不就完了嗎。 但是 仔細(xì)一想又發(fā)現(xiàn) 不對(duì)。剛剛只局限于正數(shù)的情況 可是這里還有負(fù)數(shù)呢! 所以 我們要對(duì)這選出來(lái)的五個(gè)數(shù)分情況討論。

我們要讓乘積最大 那么選出來(lái)的五個(gè)數(shù)的乘積 都盡量應(yīng)該是正數(shù) 所以 我們?nèi)绻x擇負(fù)數(shù) 那么也最好讓它成雙成對(duì)的出現(xiàn) 因?yàn)樨?fù)負(fù)得正 并且這個(gè)負(fù)數(shù)越小乘積就越大。根據(jù)此推斷 我們將這五個(gè)數(shù)分為以下幾種情況。

一：0個(gè)負(fù)數(shù) 5個(gè)正數(shù)。即選出這個(gè)數(shù)列里最大的五個(gè)數(shù)。

二：2個(gè)負(fù)數(shù) 3個(gè)正數(shù)。即選出這個(gè)數(shù)列里最大的三個(gè)數(shù)和最小的兩個(gè)數(shù)。

三：4個(gè)負(fù)數(shù) 1個(gè)正數(shù)。即選出這個(gè)數(shù)列里最大的一個(gè)數(shù)和最小的四個(gè)數(shù)。

然后我們將這三種情況算出來(lái)的乘積取一個(gè)最大值即可。

但是這樣就完了嗎？ 不你想多了。因?yàn)槿绻@ n n n個(gè)數(shù)全是負(fù)數(shù)怎么辦？

很簡(jiǎn)單 我們?yōu)榱俗尦朔e最大 我們將會(huì)選取最大的五個(gè)負(fù)數(shù)。但當(dāng)我們?cè)倩仡^看一下 發(fā)現(xiàn)這不就是第一種情況嗎？

所以 我們就不需要特判這種情況了。

代碼

#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);// 給這個(gè)數(shù)組排序 
		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;//按照思路中所講的三種情況進(jìn)行取最大值 并記得換行 
	}
	return 0;//返回 0 
}

總結(jié)

本篇文章就到這里了，希望能給你帶來(lái)幫助，也希望您能夠多多關(guān)注腳本之家的更多內(nèi)容！

最新評(píng)論