帶你粗略了解c++的最大乘積
今天給大家講最大乘積這道題目
最大乘積
內(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)容!
相關(guān)文章
C++實(shí)現(xiàn)校園導(dǎo)游系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)校園導(dǎo)游系統(tǒng),文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2022-03-03c++中l(wèi)og4cplus日志庫(kù)使用的基本步驟和示例代碼
這篇文章主要給大家介紹了關(guān)于c++中l(wèi)og4cplus日志庫(kù)使用的相關(guān)資料,log4cplus是一款開源的c++日志庫(kù),具有線程安全,靈活,以及多粒度控制的特點(diǎn),log4cplus可以將日志按照優(yōu)先級(jí)進(jìn)行劃分,使其可以面向程序的調(diào)試,運(yùn)行,測(cè)試,后期維護(hù)等軟件全生命周期,需要的朋友可以參考下2024-06-06C語(yǔ)言內(nèi)存函數(shù)的使用及其模擬實(shí)現(xiàn)
這篇文章主要介紹了C語(yǔ)言內(nèi)存函數(shù)的使用及其模擬實(shí)現(xiàn),本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2021-10-10C++進(jìn)程共享數(shù)據(jù)封裝成類實(shí)例
這篇文章主要介紹了C++進(jìn)程共享數(shù)據(jù)封裝成類的方法,以實(shí)例形式講述了其封裝代碼與具體用法,具有一定的實(shí)用價(jià)值,需要的朋友可以參考下2014-10-10C++算法學(xué)習(xí)之貪心算法的應(yīng)用
貪心算法是指,在對(duì)問(wèn)題求解時(shí),總是做出在當(dāng)前看來(lái)是最好的選擇。本文為大家準(zhǔn)備了幾個(gè)示例,從而能深入了解貪心算法的應(yīng)用,需要的可以參考一下2022-05-05C++實(shí)現(xiàn)LeetCode(30.串聯(lián)所有單詞的子串)
這篇文章主要介紹了C++實(shí)現(xiàn)LeetCode(30.串聯(lián)所有單詞的子串),本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-07-07opencv實(shí)現(xiàn)視場(chǎng)轉(zhuǎn)換
這篇文章主要為大家詳細(xì)介紹了opencv實(shí)現(xiàn)視場(chǎng)轉(zhuǎn)換,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-04-04使用C語(yǔ)言實(shí)現(xiàn)CRC校驗(yàn)的方法
本篇文章是對(duì)使用C語(yǔ)言實(shí)現(xiàn)CRC校驗(yàn)的方法進(jìn)行了詳細(xì)的分析介紹,需要的朋友參考下2013-05-05C++?計(jì)算時(shí)間差的五種方法小結(jié)
本文主要介紹了C++?計(jì)算時(shí)間差的五種方法小結(jié),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04C語(yǔ)言雙向鏈表實(shí)現(xiàn)根據(jù)使用頻率安排元素位置的功能實(shí)例代碼
這篇文章主要介紹了C語(yǔ)言雙向鏈表實(shí)現(xiàn)根據(jù)使用頻率安排元素位置的功能實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-03-03