1.題目描述

給定一個(gè)無序數(shù)組，包含正數(shù)、負(fù)數(shù)和 0，要求從中找出 3 個(gè)數(shù)的乘積，使得乘積最大，要求時(shí)間復(fù)雜度： O(n)，空間復(fù)雜度：O(1)

• 輸入描述:
  第一行是數(shù)組大小 n，第二行是無序整數(shù)數(shù)組 A[n]。n >=3
• 輸出描述:
  滿足條件的最大乘積
• 輸入示例:

  4 
  3 4 1 2
  

• 輸出示例:

  24
  

2.題目解析

數(shù)列有以下三種情況：

1. 全是正數(shù)
2. 全是負(fù)數(shù)
3. 有正有負(fù)

乘積最大只有兩種情況：

1. 三個(gè)最大正數(shù)
2. 一個(gè)最大整數(shù)和兩個(gè)最小負(fù)數(shù)

問題最終歸結(jié)為找出這五個(gè)數(shù)比較乘積即可。

3.參考答案

#include <bits/stdc++.h>
using namespace std;

int main() {
   int n = 0;
   scanf("%d",&n);
   long long nums[n];
   fill_n(nums,n,0);
   for(int i=0;i<n;++i){
       scanf("%lld",&nums[i]);
   }
   sort(nums,nums+n);
   long m = max(nums[n-1]*nums[n-2]*nums[n-3],nums[n-1]*nums[0]*nums[1]);
   printf("%lld",m);
   return 0;
}

注意:兩個(gè)long數(shù)字相乘，結(jié)果可能大于long最大值，所以，乘積放入long long，防止溢出。

牛客題目