首页 > 试题广场 >

最大乘积

[编程题]最大乘积
  • 热度指数：6787 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
给定一个无序数组，包含正数、负数和0，要求从中找出3个数的乘积，使得乘积最大，要求时间复杂度：O(n)，空间复杂度：O(1)

输入描述:
第一行是数组大小n，第二行是无序整数数组A[n]


输出描述:
满足条件的最大乘积
示例1

输入

4
3 4 1 2

输出

24
算法知识视频讲解
添加回答
Getter头像 Getter 

	input()  // 不需要数组长度，给的测试用例数组长度出错。不能100%通过





	arr =input().split(' ') 





	for i in range(len(arr)):





	    arr[i] =int(arr[i])





	arr.sort()





	if arr[0]*arr[1] > arr[-2]*arr[-3]:





	    print(arr[0]*arr[1]*arr[-1])





	else:





	    print(arr[-1] *arr[-2] *arr[-3])
发表于 2018-10-23 01:19:15 回复(2)
幸运是我头像 幸运是我 
//思路 两种情况，一是两个最小负数加一个最大正数，二是三个最大正数

import java.util.Scanner;
public class Main {
 public static void main(String[] args) {
  Scanner scanner=new Scanner(System.in);
  int nextInt = scanner.nextInt();
  long min1=0,min2=0;
  long max1=0,max2=0,max3=0;
  while(scanner.hasNext()) {
   long a = scanner.nextLong();
   if(a<0) {
    if(a<min1) {
     min2=min1;
     min1=a;
     
    }else if(a<min2) {
     min2=a;
    }
   }else if(a>=0) {
    if (a>max1) {
     max3=max2;
     max2=max1;
     max1=a;
    }else if (a>max2) {
     max3=max2;
     max2=a;
    }else if(a>max3) {
     max3=a;
    }
   }
  }
  long result=max1*max2*max3>min1*min2*max1?max1*max2*max3:min1*min2*max1;
  System.out.println(result);
 }
}

发表于 2018-08-05 18:38:24 回复(3)
Python
华科平凡头像 华科平凡

python两行

假装没看到时间复杂度要求。

  1. 先对数组进行排序
  2. 如果全为负数或全为正数，取最后三个数相乘既为最大乘积。关键是既有正数又有负数的情况（0其实可以看作负数）。如果有两个正数(例如[-2，-1，0，1，2])，那么最大值为arr[0] * arr[1] * arr[-1], 如果有一个正数(例如[-2，-1，0，2])，最大值同样为arr[0] * arr[1] * arr[-1]。
  3. 结合上面两种情况，只需要取max(arr[-1] * arr[-2] * arr[-3], arr[0] * arr[1] * arr[-1])
length, arr = input(), sorted(map(int, input().split()))
print(max(arr[-1] * arr[-2] * arr[-3],  arr[0] * arr[1] * arr[-1]))
编辑于 2019-03-02 10:54:20 回复(0)
pein531头像 pein531
最大值只有以下两种情况，它两谁大选谁
1.三个最大的正数相乘。
2.两个最小的负数相乘，然后再和最大的正数相乘。
可以采用O(n)的复杂度找出前三大的正数和前二小的负数： 
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        // 使用O(n)的复杂度，同时计算最大的三个值和最小的两个值
        long max1 = Long.MIN_VALUE, max2 = Long.MIN_VALUE, max3 = Long.MIN_VALUE;
        long min1 = Long.MAX_VALUE, min2 = Long.MAX_VALUE;
        for(int i = 0; i < n; i++){
            long num = sc.nextLong();
            // 最大的三个数
            if(num > max1){
                max3 = max2;
                max2 = max1;
                max1 = num;
            }else if(num > max2) {
                max3 = max2;
                max2 = num;
            }else if(num > max3)
                max3 = num;
            // 最小的两个数
            if(num < min1){
                min2 = min1;
                min1 = num;
            }else if(num < min2)
                min2 = num;
        }
        // 最大值要么是三个最大正数相乘，要么是两个最小负数和最大正数相乘
        System.out.println(Math.max(max1*max2*max3, min1*min2*max1));
    }
}
当然，为了在笔试的时候节省时间去AC，也可以无视题目中的复杂度要求，直接采用偷懒的办法 
n = int(input())
arr = sorted(list(map(int, input().split())))
print(max(arr[-3]*arr[-2]*arr[-1], arr[0]*arr[1]*arr[-1]))


发表于 2021-02-01 15:01:46 回复(0)
C/C++
nbgao头像 nbgao 
#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    long x, max1=0, max2=0, max3=0, min1=0, min2=0;
    scanf("%d", &n);
    for(int i=0;i<n;i++){
        scanf("%ld", &x);
        if(x>=max1){
            max3 = max2;
            max2 = max1;
            max1 = x;
        }else if(x>=max2){
            max3 = max2;
            max2 = x;
        }else if(x>=max3)
            max3 = x;
        else if(x<=min1){
            min2 = min1;
            min1 = x;
        }else if(x<=min2)
            min2 = x;
    }
    printf("%ld\n", max1*max(max2*max3, min1*min2));    
    return 0;
}

发表于 2020-11-13 00:25:16 回复(0)
C/C++
茶月猫头像 茶月猫
思路还是原来的思路：sort完数组之后，res1=最大的*次大*第三大的；res2=最小*次小*第三小的，比较输出两个值中最大的值。
【注意】本题有个坑，输入的数据是long long型的（通过率100%），如果换成int，通过率只有40%，所以在计算res时，也是long long 类型。【emm...神坑 
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(void)
{
    int len;
    long long itemp;
    cin >> len;
    vector<long long> data(len);
    for (int i = 0; i < len; i++)
    {
        cin >> itemp;
        data[i] = itemp;
    }
    sort(data.begin(), data.end());
    if (len >= 3)
    {
        long long res1 = data[len - 1] * data[len - 2] * data[len - 3];
        long long res2 = data[0] * data[1] * data[len - 1];
        if (res1 > res2)
            cout << res1 << endl;
        else
            cout << res2 << endl;
    }
    else
        cout << 0 << endl;
    return 0;
}

发表于 2019-04-30 15:46:49 回复(2)
一剑光寒十九粥头像 一剑光寒十九粥 
    from functools import reduce
    n =int(input())
    nums =list(map(lambdax : int(x), input().split(' ')))
    nums.sort()
    if 0 in nums:
        print(max([0, reduce(lambdax, y: x *y, nums[n-3:n]), reduce(lambdax, y: x *y, nums[0:2] +[nums[-1]])]))
    else:
        print(max([reduce(lambdax, y: x *y, nums[n-3:n], 1), reduce(lambdax, y: x *y, nums[0:2] +[nums[-1]])]))
发表于 2018-09-02 12:47:18 回复(0)
Python
我要扛offer回家头像 我要扛offer回家 
import sys
n=int(sys.stdin.readline().strip())
arr=list(map(int,sys.stdin.readline().strip().split()))
arr.sort()
res=max(arr[0]*arr[1]*arr[-1],arr[-1]*arr[-2]*arr[-3])
print(res)

发表于 2019-04-03 11:45:30 回复(0)
YC2018头像 YC2018 
//思路 两种情况，一是两个最小负数加一个最大正数，二是三个最大正数
#include<iostream>
using namespace std;
int main()
{
    int n;
    while(cin>>n)
    {
        long t;
        long fu1=0;long fu2=0;
        long z1=0;long z2=0;long z3=0;
        for(int i=0;i<n;i++)
        {
            cin>>t;
            if(t<0)
            {
                if(t<fu1)   //最小负数
                {
                    fu2=fu1;
                    fu1=t;
                }
                else if(t<fu2) //次小负数
                    fu2=t;
            }
            else  //找最大三个正数
            {
       
                if(t>z1)
                {
                    z3=z2;
                    z2=z1;
                    z1=t;
                    
                }
                else if(t>z2)
                {
                    z3=z2;
                    z2=t;
                }
                else if(t>z3)
                    z3=t;
            }
        }
        long long result1=fu1*fu2*z1;
        long long result2=z1*z2*z3;
        long long max=result1>result2?result1:result2;
        cout<<max<<endl;
    }
    return 0;
}

发表于 2018-07-05 10:17:01 回复(2)
ChessC头像 ChessC
不知道这种题的样例老是要在int和long long这种数据类型上面做文章有什么意义。你给定了int，样例就老老实实给int能过的不好吗？
发表于 2019-02-20 14:53:36 回复(0)
Samuelyo头像 Samuelyo 
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            long len = sc.nextLong();
            Long min1 = Long.MAX_VALUE;
            Long min2 = Long.MAX_VALUE;
            Long min3 = Long.MAX_VALUE;
            Long max1 = Long.MIN_VALUE;
            Long max2 = Long.MIN_VALUE;
            Long max3 = Long.MIN_VALUE;
            for (int i = 0; i < len; i++) {
                long cur = sc.nextLong();
                if (i == 0) {
                    min1 = Math.min(min1, cur);
                    max1 = Math.max(max1, cur);
                } else if (i == 1) {
                    max2 = Math.max(max2, (cur > 0 ? max1 : min1) * cur);
                    min2 = Math.min(min2, (cur > 0 ? min1 : max1) * cur);
                    min1 = Math.min(min1, cur);
                    max1 = Math.max(max1, cur);
                } else {
                    max3 = Math.max(max3, (cur > 0 ? max2 : min2) * cur);
                    min3 = Math.min(min3, (cur > 0 ? min2 : max2) * cur);
                    max2 = Math.max(max2, (cur > 0 ? max1 : min1) * cur);
                    min2 = Math.min(min2, (cur > 0 ? min1 : max1) * cur);
                    min1 = Math.min(min1, cur);
                    max1 = Math.max(max1, cur);
                }
            }
            System.out.println(max3);
        }
        sc.close();
    }

}
发表于 2018-05-21 16:21:46 回复(0)
已注销头像 已注销
res1=最大的*次大*第三大的；res2=最小*次小*第三小的，比较输出两个值中最大的值。
真正 o(n) 的算法。
利用 nth_element 函数求出需要的值。nth_element 使用快速选择算法实现的，复杂度是O(N).
注意long long
#include <iostream>
#include<algorithm>
using namespace std;
const int N = 200010;
long long a[N];
long long n;
int main(){
    cin>> n;
    for(int i = 0; i < n; i++){
        cin >> a[i];
    }
    if(n <= 3){
        if(n == 0){
            cout << 0 << endl;
            return 0;
        }
        long long res = 1;
        for(int i = 0; i < n; i++) res *= a[i];
        cout << res << endl;
        return 0;
    }
    nth_element(a,a + 1,a + n);
    long long  l1 = a[1];
    nth_element(a, a,a + n);
    long long  l2 = a[0];
    
    nth_element(a, a + n - 1 ,a + n);
    long long  m1 = a[n - 1];
    nth_element(a, a + n - 2 ,a + n);
    long long  m2 = a[n - 2];
    nth_element(a, a + n - 3,a + n);
    long long  m3 = a[n - 3];
    long long res = 0;
    res = l1 * l2 * m1;
    res = res > m1 * m2 * m3 ? res : (long long)m1 * m2 * m3 ;

    cout << res;
    return 0;
    
    
}


发表于 2021-12-15 23:48:49 回复(0)
牛客579118352号头像 牛客579118352号 
n = int(input())
a = list(map(int,input().split()))
a.sort()
print(max(a[0]*a[1]*a[-1],a[-1]*a[-2]*a[-3],a[0]*a[-1]*a[-2]))

发表于 2021-04-26 22:09:03 回复(0)
Creative头像 Creative
//ac。两种情况：一：寻找最小的两个负数和一个最大的正数。（因为要乘积最大，负数的个数必须是双数个，双数负数乘积为正）。
//二：三个最大正数。
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include<bits/stdc++.h> 

using namespace std;
int main(){
    int n;
    while(cin>>n){
        vector<int> re;
        int t;
        while(n){
            n--;
            cin>>t;
            re.push_back(t);
        }

        long long ma=0;
        int m1=0,m2=0,m3=0;
        int f1=0,f2=0;
        for(int i=0;i<re.size();i++){
            int a=re[i];
            if(a<f1){
                f2=f1;
                f1=a;
                
            }else if(a>=f1 && a<f2){
                f2=a;
            }
            
            if(a>m1){
                m3=m2;
                m2=m1;
                m1=a;
            }else if(a<=m1 && a>m2){
                m3=m2;
                m2=a;
            }else if(a<=m2 && a>m3){
                m3=a;
            }
            
        }
        
        if(f1<0 && f2<0){
            ma=max((long long)f1*f2*m1,(long long)m3*m2*m1);

        }else{
            ma=m3*m2*m1;
        }
        cout<<ma<<endl;
    }
    return 0;
}
发表于 2020-08-31 10:58:54 回复(0)
牛客238833152号头像 牛客238833152号 
def find_some_largest_numbers(nums, n):
    if n == 2:
        one = two = -2 ** 31
        for n in nums:
            if n >= one:
                one, two = n, one
            elif n >= two:
                two = n
                 
        return one, two
    elif n == 3:
        one = two = three = -2 ** 31
        for n in nums:
            if n >= one:
                one, two, three = n, one, two
            elif n >= two:
                two, three = n, two
            elif n >= three:
                three = n
                 
        return one, two, three
     
n = int(input())
nums = [int(i) for i in input().split()]
 
negs, zeros, pos = [], [], []
for n in nums:
    if n < 0:
        negs.append(n)
    elif n == 0:
        zeros.append(n)
    else:
        pos.append(n)

if not pos:
    if not zeros:
        first, second, third = find_some_largest_numbers(negs, 3)
        print(first * second * third)
    else:
        print(0)
else:
    if len(pos) > 2:
        first, second, third = find_some_largest_numbers(pos, 3)
          
        purePosMax = first * second * third
        maxPos = first
    else:
        purePosMax = 0
        maxPos = max(pos)

    if len(negs) > 1:
        absNegs = [abs(i) for i in negs]
        first, second = find_some_largest_numbers(absNegs, 2)
         
        maxTwoNegs = first * second
    else:
        maxTwoNegs = 0

    print(max(purePosMax, maxPos * maxTwoNegs))

发表于 2020-08-01 22:50:00 回复(0)
MG_Reading头像 MG_Reading 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e4+10;
const int INF = 0x7f7f7f7f;
//因为要求用o(n)时间复杂度 所以不能用sort()
int main(){
    int n;
    int a[MAXN];
    while(~scanf("%d", &n)){//找出最小的两个和最大的三个数 不需要区分正负
        long long b1, b2, c1, c2, c3;
        b1=b2=INF;
        c1=c2=c3=-INF;
        for(int i=0; i<n; i++){
            scanf("%d", &a[i]);
            if(a[i]>c3) c1=c2, c2=c3, c3=a[i];
            else if(a[i]>c2) c1=c2, c2=a[i];
            else if(a[i]>c1) c1=a[i];
            if(a[i]<b1) b2=b1, b1=a[i];
            else if(a[i]<b2) b2=a[i];
        }
        long long x=b1*b2*c3, y=c1*c2*c3;
        printf("%lld\n", max(x, y));
    }
    return 0;
}

编辑于 2020-07-23 13:31:51 回复(0)
字节研发工程师头像 字节研发工程师 
import java.util.Arrays;
import java.util.Scanner;

/**
 * 思路：先排序。两最小负一正；三正
 * 坑：输入数值为long类型，千万千万注意，否则通过率只有22.2%！
 */

public class No4MaxThreeMulti {
    public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        int n=scanner.nextInt();
//        int[]  arr=new int[n];
        long[]  arr=new long[n];
        for (int i = 0; i < n; i++) {
            arr[i]=scanner.nextInt();
        }
        Arrays.sort(arr);
        long neg=arr[0]*arr[1]*arr[n-1];
        long pos=arr[n-1]*arr[n-2]*arr[n-3];
        System.out.println(neg>pos?neg:pos);
    }
}

发表于 2020-03-20 21:23:44 回复(0)
times_头像 times_ 
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextLong();
        }
        Arrays.sort(arr);
        long res = 0;
        if (arr[0] * arr[1] > arr[n - 2] * arr[n - 3])
            res = arr[0] * arr[1] * arr[n - 1];
        else
            res = arr[n - 3] * arr[n - 2] * arr[n - 1];
        System.out.println(res);
    }

}
发表于 2019-08-23 21:14:51 回复(0)
C/C++
海问香12138头像 海问香12138

int不够大，long够不够要看具体环境，所以要用long long 

#include <stdio.h>

long long n,x;

long long MAX(long long x,long long y);

int main()
{
	long long i,min=0,min2=0,max3=0,max2=0,max=0;
	scanf("%lld",&n);
	for(i=0;i<n;i++)
	{
		scanf("%lld",&x);
		if(x>max)
		{
			max3 = max2;
			max2 = max;
			max = x;
		}
		else if(x>max2)
		{
			max3 = max2;
			max2 = x;
		}
		else if(x>max3)
			max3 = x;
		else if(x<min)
		{
			min2 = min;
			min = x;
		}
		else if(x<min2)
			min2 = x;
	}
	printf("%lld\n",MAX(max3*max2*max,max*min*min2));
	return 0;
}

long long MAX(long long x,long long y)
{
	return x>y?x:y;
}


发表于 2019-08-22 09:34:05 回复(0)
牛客690304937头像 牛客690304937 
n = int(input())
nums = list(map(int, input().strip().split()))

max1 = max(nums[:3])
max3 = min(nums[:3])
max2 = sum(nums[:3]) - max1 - max3

min1 = max3
min2 = max2

for n in nums[3:]:
    if n > max1:
        max3 = max2
        max2 = max1
        max1 = n
    elif n > max2:
        max3 = max2
        max2 = n
    elif n > max3:
        max3 = n

    if n < min1:
        min2 = min1
        min1 = n
    elif n < min2:
        min2 = n

x1 = max1 * max2 * max3
x2 = max1 * min1 * min2
print(x1 if x1 > x2 else x2)
发表于 2019-07-27 23:54:26 回复(0)
提交观点

问题信息

C++工程师 golang工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 贪心 模拟 2018 拼多多集团-PDD Java工程师
上传者：小小
难度：
37条回答 10253浏览

热门推荐

通过挑战的用户

查看代码

相关试题

最大乘积

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号