帶你粗略瞭解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的更多內容!