首页 > 试题广场 >

三个数的最大乘积

[编程题]三个数的最大乘积

热度指数：28119 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个长度为 $n$ 的无序数组 $A$ ，包含正数、负数和 0 ，请从中找出 3 个数，使得乘积最大，返回这个乘积。

要求时间复杂度： $O(n)$ ，空间复杂度： $O(1)$ 。

数据范围：

$3 \le n \le 10^4$

$-10^4 \le A[i] \le 10^4$

示例1

输入

[3,4,1,2]

输出

算法知识视频讲解

Java

牛客839384289号

    public long solve (int[] A) {
        // write code here
        int len=A.length;
        Arrays.sort(A);
        return Math.max((long)A[len-1]*A[len-2]*A[len-3] ,(long)A[len-1]*A[0]*A[1]);
    }

编辑于 2024-03-24 14:44:23 回复(0)

Java

blue&&lan

Api工程师 : )

public long solve (int[] A) {
        Arrays.sort(A);
        if((A[0]*A[1])>=(A[A.length-2]*A[A.length-3]))
            return (long)A[0]*(long)A[1]*(long)A[A.length-1];
        return (long)A[A.length-1]*(long)A[A.length-2]*(long)A[A.length-3];
    }

发表于 2022-04-25 17:06:16 回复(0)

Java

益塘

import java.util.*;


public class Solution {
    /**
     * 最大乘积
     * @param A int整型一维数组 
     * @return long长整型
     */
    public long solve (int[] A) {
        // write code here
        Arrays.sort(A);//排序，排序后取最小两个数和最大数的乘积与三个最大数相比取大者返回
        long a=A[A.length-1];
        long b=A[A.length-2];
        long c=A[A.length-3];
        long d=A[0];
        long e=A[1];
        if(a*b*c>a*d*e)
        return a*b*c;
        else
            return a*d*e;
    }
}

发表于 2022-04-14 14:35:18 回复(0)

Java

Java小将

public long solve (int[] A) { // write code here
long ans=0;
int n=A.length;
java.util.Arrays.sort(A);
if((long)A[n-1]*A[n-2]*A[n-3]>(long)A[0]*A[1]*A[n-1]){
ans=(long)A[n-1]*A[n-2]*A[n-3];}
else{
ans=(long)A[0]*A[1]*A[n-1];
}
return ans;
}

发表于 2022-01-12 21:48:31 回复(0)

Java

老农爱编程

public long solve (int[] A) {
        // write code here
        int fushu_count = 0; //出现负数的个数
        int zhengshu_count = 0; //出现正数的个数
        int zero_count = 0; //出现0的个数
        int res_max = Integer.MIN_VALUE;
        List<Integer> sortList = new ArrayList<Integer>();
        for(int i : A){
            sortList.add(i);
            if(i < 0){
                fushu_count ++;
            }else if(i > 0 ){
                zhengshu_count ++;
            }else{
                zero_count ++;
            }
        }
        //进行排序
        Collections.sort(sortList);
        //有0 有正 有负 此时可能最大的是这几种组合：
        //1、最前面的两个和最后一个
        //2、最后面的三个
        //3、0
        if(fushu_count >0 || zhengshu_count >0 || zhengshu_count >0){
            //全是负数
            if(zhengshu_count == 0 && zero_count == 0 && fushu_count > 0){
            long max6 = (long)sortList.get(sortList.size() - 1) 
                * sortList.get(sortList.size() - 2) 
                * sortList.get(sortList.size() - 3);
                return max6;
            }
            //两负一正
            long max1 = (long)sortList.get(sortList.size() - 1)
                * sortList.get (0)
                * sortList.get(1);
            //全正
            long max2 = (long)sortList.get(sortList.size() - 1) 
                * sortList.get(sortList.size() - 2) 
                * sortList.get(sortList.size() - 3);
            //例如那种-1 2 2 0
            long max3 = 0;
            long max4 = Math.max(max1,max2);
            long max5 = Math.max(max4,max3);
            return max5;
        }
        return 0;
    }

发表于 2022-01-06 14:27:22 回复(0)

Java

牛客465248204号

挺简单的，就只需考虑全正或者两负两种情况

import java.util.*;
public class Solution {
    public long solve (int[] A) {
        Arrays.sort(A);
        int len = A.length-1;
        return Math.max((long)A[len]*A[len-1]*A[len-2],(long)A[0]*A[1]*A[len]);
    }
}

发表于 2022-01-01 12:23:25 回复(0)

Java

牛客491926010号

import java.util.*;

public class Solution {
/**
* 最大乘积
* @param A int整型一维数组
* @return long长整型
*/
public long solve (int[] A) {
// write code here
Arrays.sort(A);
return Math.max(1L*A[0]*A[1]*A[A.length-1] ,1L*A[A.length-1] * A[A.length-2] * A[A.length-3]);
}
}

发表于 2021-11-21 02:59:06 回复(0)

Java

牛客654583284号

有大佬可以指点一下，这个是为什么吗？用例值太大了吗？改为1000输出就没问题，为什么10000实际输出就不对呢？

Arrays.sort(A);

int n = A.length;

return Math.max((long)(A[n-1]*A[n-2]*A[n-3]),(long)(A[n-1]*A[0]*A[1]));

用例：[10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000,10000]

预计输出：1000000000000

实际输出：-727379968

发表于 2021-11-07 19:25:21 回复(1)

Java

waigo

这最后一个用例是不是有问题，输入

[-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000,-10000]

答案竟然是-1000000000000

发表于 2021-11-07 17:39:24 回复(3)

Java

光钻

public long solve (int[] a) {
// write code here
int m = a.length-1;
Arrays.sort(a);

Long Max1 = ((long)(a[m] * a[m - 1]) * a[m - 2]);
Long Max2 = ((long) (a[0] * a[1]) * a[m]);

return Max1>Max2?Max1:Max2;
}

发表于 2021-10-22 13:56:05 回复(0)

Java

快快快嘟嘟嘟

只有两种可能：三个正；两个负加一个正；所以排序之后相乘再比较就好：

 public long solve (int[] A) {
               // write code here
        int length = A.length;
        ArrayList<Long> a=new ArrayList<>(length);
        for (int i : A) {
            a.add((long) i);
        }
        Collections.sort(a);
        System.out.println(a);
        long MaxOne=a.get(length-1)*a.get(length-2)*a.get(length-3);
        long MaxTwo=a.get(0)*a.get(1)*a.get(length-1);
        return (MaxOne>MaxTwo)?MaxOne:MaxTwo;
    
    }

发表于 2021-09-25 18:18:43 回复(0)

Java

惠灵顿靖

    public long solve (int[] A) {
        // write code here
        int len=A.length;
        Arrays.sort(A);
        long max=Math.max((long)A[len-1]*(long)A[len-2]*(long)A[len-3],(long)A[len-1]*(long)A[0]*(long)A[1]);
        return max;
    }

发表于 2021-08-20 20:46:07 回复(0)

Java

寒烟画屏幽

必须用long，不然会溢出

import java.util.*;

public class Solution {
/**
* 最大乘积
* @param A int整型一维数组
* @return long长整型
*/
public long solve (int[] A) {
// write code here

Arrays.sort(A);

int max1=A[A.length-1],max2=A[A.length-2],max3=A[A.length-3];
int min1=A[0],min2=A[1];
System.out.print(max1);
return Math.max((long)min1*min2*max1,(long)max1*max2*max3);
}
}

发表于 2021-06-25 15:11:41 回复(0)

Java

肥猿

解题思路：遍历数组，找到最大的三个数和最小的两个数，三个数的最大乘积来源可能有两种，一种是三个最大的数相乘，另一种是两个最小的数和一个最大的数相乘

import java.util.*;
public class Solution {
    /**
     * 最大乘积
     * @param A int整型一维数组 
     * @return long长整型
     */
    public long solve (int[] A) {
        // write code here
        int max1=Integer.MIN_VALUE,max2=Integer.MIN_VALUE,max3=Integer.MIN_VALUE;
        int min1=Integer.MAX_VALUE,min2=Integer.MAX_VALUE;
        for(int num:A){
            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;
        }
        return Math.max((long)max1*max2*max3,(long)max1*min1*min2);
    }
}

发表于 2021-03-20 13:28:20 回复(0)

Java

罗尼玛

import java.util.*;

public class Solution {
    public long solve (int[] A) {
        Arrays.sort(A);
        return Math.max((long)A[0]*A[1]*A[A.length-1],(long)A[A.length-3]*A[A.length-2]*A[A.length-1]);
    }
}

发表于 2020-11-25 19:15:15 回复(0)