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

更新時間：2021年08月20日 15:30:20 作者：咸魚吖

這篇文章主要為大家詳細介紹了C++的最大乘積，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能給你帶來幫助

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

最大乘積

內存限制：256 MiB

時間限制：1000 ms

輸入文件：maximum.in

輸出文件：maximum.out

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

評測方式：文本比較　　

題目描述

給你 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

思路

這個題目其實不難。我們先分析一下這個題目。

這個題目要我們從一組數據中選取五個數使得這五個數乘積最大。

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

我們要讓乘積最大那么選出來的五個數的乘積都盡量應該是正數所以我們如果要選擇負數那么也最好讓它成雙成對的出現因為負負得正并且這個負數越小乘積就越大。根據此推斷我們將這五個數分為以下幾種情況。

一：0個負數 5個正數。即選出這個數列里最大的五個數。

二：2個負數 3個正數。即選出這個數列里最大的三個數和最小的兩個數。

三：4個負數 1個正數。即選出這個數列里最大的一個數和最小的四個數。

然后我們將這三種情況算出來的乘積取一個最大值即可。

但是這樣就完了嗎？不你想多了。因為如果這 n n n個數全是負數怎么辦？

很簡單我們?yōu)榱俗尦朔e最大我們將會選取最大的五個負數。但當我們再回頭看一下發(fā)現這不就是第一種情況嗎？

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

代碼

#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 
}