帶你粗略瞭解c++的最大乘積
今天給大傢講最大乘積這道題目
最大乘積
內存限制：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個數全是負數怎麼辦？
很簡單 我們為瞭讓乘積最大 我們將會選取最大的五個負數。但當我們再回頭看一下 發現這不就是第一種情況嗎？
所以 我們就不需要特判這種情況瞭。
代碼
#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
}
總結
本篇文章就到這裡瞭，希望能給你帶來幫助，也希望您能夠多多關註WalkonNet的更多內容！