帶你粗略了解c++的最大乘積

第帶你粗略了解c++的最大乘積目錄今天給大家講最大乘積這道題目樣例

思路代碼總結(jié)

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

最大乘積

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

時(shí)間限制：1000ms

輸入文件：maximum.in

輸出文件：maximum.out

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

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

題目描述

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

輸入格式

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

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

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

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

輸出格式

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

樣例

樣例輸入

4

5

-1-2-3-4-5

6

-1-2-312-1

6

-1000-1-1

6

-9-7-5-3-21

樣例輸出

-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)槿绻@nnn個(gè)數(shù)全是負(fù)數(shù)怎么辦？

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

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

代碼

#includebits/stdc++.h

usingnamespacestd;

longlonga[100005];

intn;

intt;

intmain()

freopen("maximum.in","r",stdin);

freopen("maximum.out","w",stdout);

//文件名輸入輸出

cint;

while(t--)

cinn;

for(inti=1;i++i)

cina[i];

//輸入

sort(a+1,a+n+1);//給這個(gè)數(shù)組排序

coutmax(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;//按照思