[10]最大乘积-拼多多2018

1.题目描述

给定一个无序数组，包含正数、负数和 0，要求从中找出 3 个数的乘积，使得乘积最大，要求时间复杂度： O(n)，空间复杂度：O(1)

• 输入描述:
  第一行是数组大小 n，第二行是无序整数数组 A[n]。n >=3
• 输出描述:
  满足条件的最大乘积
• 输入示例:

  4 
  3 4 1 2
  

• 输出示例:

  24
  

2.题目解析

数列有以下三种情况：

1. 全是正数
2. 全是负数
3. 有正有负

乘积最大只有两种情况：

1. 三个最大正数
2. 一个最大整数和两个最小负数

问题最终归结为找出这五个数比较乘积即可。

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

注意:两个long数字相乘，结果可能大于long最大值，所以，乘积放入long long，防止溢出。

牛客题目