首页 > 试题广场 >

最大乘积

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

输入描述:
输入共2行,第一行包括一个整数n,表示数组长度
第二行为n个以空格隔开的整数,分别为A1,A2, … ,An


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

输入

4
3 4 1 2

输出

24
#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
long long helper(vector<int>& A)
{
    const int n =A.size();
    if(n < 3) return 0;
    make_heap(A.begin(),A.end(),greater<int>());
    long long min1 =A[0];
    pop_heap(A.begin(),A.end(),greater<int>());
    long long min2 =A[0];

    make_heap(A.begin(),A.end());
    long long max1 =A[0];
    pop_heap(A.begin(),A.end());
    long long max2 =A[0];
    pop_heap(A.begin(),A.end()-1);
    long long max3 =A[0];
    return max(min1*min2*max1,max1*max2*max3);
}
            
int main()
{
    int n;
    cin>>n;
    vector<int> input(n);
    for(int i =0; i< n; ++i) cin>>input[i];
    cout<<helper(input);
    return 0;
}

利用堆排序,构建堆O(n)时间,提取最大3个数和最小2个数,O(5log(n)),总时间O(n)。

发表于 2017-08-11 10:42:38 回复(2)
#python 可以对list排序,所以排序完找前三个和后两个乘一下,输出较大的一个。
#本来以为空间会超,结果没有,好吧。

n=int(input())
str2=input()
list=str2.split(" ")
a=[]
for i in list:
    a.append(int(i))
a.sort(reverse=True)
print(max(a[0]*a[1]*a[2] , a[n-1]*a[n-2]*a[0]))

发表于 2019-01-21 01:50:17 回复(2)
//自我感觉这么做最简单
import java.util.Arrays;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
// TODO Auto-generated method stub
Scanner flat = new Scanner(System.in);
int n = flat.nextInt();
long[] arr= new long[n];
for(int i=0;i<arr.length;i++){
arr[i]=flat.nextLong();  
}
Arrays.sort(arr);
long num1=arr[n-1]*arr[n-2]*arr[n-3];
        long num2=arr[n-1]*arr[0]*arr[1];
  
        long max=Math.max(num1,num2);
        System.out.print(max);
}
}

发表于 2017-08-08 22:59:08 回复(1)
//AC代码:
#include<stdio.h>
#include<algorithm>
using namespace std;
int main(){
    int N,i;
    while(scanf("%d",&N)!=EOF){
        vector<long long> d(N);
        for(i=0;i<N;i++) scanf("%lld",&d[i]);
        sort(d.begin(),d.end());
        printf("%lld\n",max(d[0]*d[1]*d[N-1],d[N-1]*d[N-2]*d[N-3]));
    }
}

发表于 2017-08-06 10:42:50 回复(8)
#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-09 00:37:52 回复(0)
import java.util.ArrayList;
import java.util.Comparator;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        ArrayList<Long> list = new ArrayList<>();
        for(int i = 0; i<n; i++){
            list.add(sc.nextLong());
        }
        list.sort(new Comparator<Long>() {
            @Override
            public int compare(Long a, Long b) {
                return (a<b)?-1:1;
            }
        });
        System.out.println(result(list));
    }

    private static Long result(ArrayList<Long> list) { // 想要最大一定要在两头取,要么取三个最大值(正数)相乘,要么选两个最小值(负数)乘上最大值
        Long a = list.get(list.size()-1)*list.get(list.size()-2)*list.get(list.size()-3);
        Long b = list.get(0)*list.get(1)*list.get(list.size()-1);
        return (a > b)?a:b;
    }
}

发表于 2020-04-05 16:49:35 回复(0)
两个思路
思路一:
时间复杂度为O(n),空间复杂度O(1)
从vecotr里面找出前三个最大数,分别表示max1>=max2>=max3, 最小的两个数min1<=min2 
就是求 max(max1*max2*max3, min1*min2*max1)
注意:防止溢出

思路二:
思路如一,不过这里用到了 sort 排序 求三个最大值和两个最小值, 时间复杂度为O(nlgn)
时间复杂度为O(nlgn),空间复杂度O(1)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
    int num = 0;
    while(cin>>num)
    {
        vector<int> vec;
        int tmpNum = 0;
        for(size_t i=0;i<num;i++)
        {
            cin>>tmpNum;
            vec.push_back(tmpNum);
        }
        
        sort(vec.begin(), vec.end());
        
        long long tmpMax = max(long(vec[0])*long(vec[1])*long(vec[vec.size()-1]), long(vec[vec.size()-1])*long(vec[vec.size()-2])*long(vec[vec.size()-3]));
        cout<<tmpMax<<endl;
        return 0;
        
    }
}


编辑于 2019-10-30 22:51:07 回复(0)
#include "iostream"
#include "algorithm"
using namespace std;
 
long long a[100000005] = {0};
 
int main(){
    long long n,i,j,s1,s2,s3,s4;
    int flag = 0;
    cin>>n;
    for(i = 0;i < n; i++){
        cin>>a[i];
        if(a[i] == 0)
        flag = 1;
    }
    sort(a,a+n);
    s1 = a[0] * a[1] * a[n-1];
    s2 = a[0] * a[n-1] * a[n-2];
    s3 = a[n-1] * a[n-2] * a[n-3];
    if(flag == 0){
        cout<<max(s1,max(s2,s3))<<endl;
    }
    else{
        s4 = max(s1,max(s2,s3));
        if(s4 < 0)
        cout<<0<<endl;
        else
        cout<<s4<<endl;
    }
    return 0;
}

发表于 2019-09-20 11:17:09 回复(0)
//利用包装类Collections提供的sort方法。  import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main { public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); if (n < 3) { return;
        }
        ArrayList<Long> list = new ArrayList<>(); for (int i = 0; i < n; i++) {
            list.add(scanner.nextLong());
        }
        Collections.sort(list); long max = list.get(list.size() - 1) * list.get(list.size() - 3) * list.get(list.size() - 2); long min = list.get(0) * list.get(1) * list.get(list.size() - 1);
        max = max > min ? max : min;

        System.out.println(max);

    }
}


发表于 2019-09-07 16:03:52 回复(0)
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
    Scanner sc=new Scanner(System.in);
    ArrayList <Long>array=new ArrayList<Long>();
    Long n=sc.nextLong();
    while(sc.hasNext()) {
        array.add(sc.nextLong());
    }
    Collections.sort(array);
    int j=-1;
  for(int i=0;i<array.size();i++) {
      if(array.get(i)>0) {j=i;}
  }
    if(j==0||j==-1||j==1) System.out.println(array.get(array.size()-1)*array.get(array.size()-2)*array.get(array.size()-3));
    else{
        Long s=array.get(0)*array.get(1)*array.get(array.size()-1);
        Long m=array.get(array.size()-1)*array.get(array.size()-2)*array.get(array.size()-3);
        if(s>m) {System.out.println(s);}
        else{System.out.println(m);}
发表于 2019-07-30 20:45:37 回复(0)
站在巨人的肩膀上--思路:分三种情况
1.数组全为正数
2.数组元素全为负数
3数组元素有正有负(ps:素组元素为0的情况没有影响)
那么,分情况讨论,为了能够覆盖所有情况,先排序,然后维护一个结果列表,分别把可能的最大结果保存下来,然后比较,取出最大值。排序是升序,结果列表存四个数:开头三个数的积、结尾三个数的积、前两个数和最后一个数的积、第一个数和后两个数的积。这四种积,包含了所有可能出现最大积的情况,再在结果列表中选出最大的积即可。采用了python默认的sorted函数,按道理时间复杂度超过O(n)了,但也AC了。
n = int(input())
l = map(int,input().split())
l = sorted(l)
res = max(l[0]*l[1]*l[2],l[-3]*l[-2]*l[-1],l[0]*l[1]*l[-1],l[0]*l[-2]*l[-1])
print(res)

发表于 2019-06-28 08:52:47 回复(3)
//最大的三个和最小的两个--最大的三个相乘 or 最小的两个*最大的
#include 
using namespace std;
int main()
{
    int n, num;
    cin >> n;
    vector vec;
    for (int i = 0; i < n; ++i){
        cin >> num;
        vec.push_back(num);
    }
    sort(vec.begin(), vec.end());
    long long sAns1 = vec[n-2] * vec[n-3];
    long long ans1  = sans1 * vec[n-1];
    long long sAns2 = vec[0] * vec[1];
    long long ans2  = sans2 * vec[n-1];
    long long ans   = max(ans1, ans2);
    cout << ans << endl;
    return 0;
}
编辑于 2019-06-20 16:32:26 回复(0)
import java.util.Scanner;

public class Main {

    public static long process(long[] arr) {
        long neg1 = 0;
        long neg2 = 0;
        long pos1 = 0;
        long pos2 = 0;
        long pos3 = 0;

        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) {
                if (arr[i] < neg1) {
                    neg2 = neg1;
                    neg1 = arr[i];
                } else if (arr[i] < neg2) {
                    neg2 = arr[i];
                }
            } else {
                if (arr[i] > pos3) {
                    pos1 = pos2;
                    pos2 = pos3;
                    pos3 = arr[i];
                } else if (arr[i] > pos2) {
                    pos1 = pos2;
                    pos2 = arr[i];
                } else if (arr[i] > pos1) {
                    pos1 = arr[i];
                }
            }
        }

        long res1 = neg1 * neg2 * pos3;
        long res2 = pos1 * pos2 * pos3;
        return res1 > res2 ? res1 : res2;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] arr = new long[n];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextLong();
        }
        System.out.println(process(arr));
    }
}
发表于 2019-06-17 16:00:38 回复(0)
var num = [3,4,1,2];
for(var i =0; i<num.length; i++){
    for(var j =0; j<num.length; j++){
        if(num[i]>num[j]){
            var all = num[i];
            num[i] = num[j];
            num[j] = all;
        }
    }
}
console.log(num[0]*num[1]*num[2]);


发表于 2019-05-24 14:39:04 回复(0)
import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n];
        for(int j=0;j<n;j++){
            arr[j]=sc.nextInt();
        }
        //排序
        int temp;
        for(int i=0;i<n;i++){
            for(int j=1;j<n-i;j++){
                if(arr[j]<arr[j-1]){
                    temp = arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                }
            }
        }
        //排序完成后.
//        for(int i=0;i<n;i++){
//            System.out.print(arr[i]+" ");
//        }
        
        if(arr[0] < 0 && arr[1]<0 && arr[n-1] > 0){
            if((Math.abs(arr[0])*Math.abs(arr[1])) > arr[n-3]*arr[n-2]){
                long lon1 = new Integer(Math.abs(arr[0])).longValue();
                long lon2 = new Integer(Math.abs(arr[1])).longValue();
                long lon3 = new Integer(arr[n-1]).longValue();
                System.out.println(lon1*lon2*lon3);
            }else{
                long lon1 = new Integer(arr[n-3]).longValue();
                long lon2 = new Integer(arr[n-2]).longValue();
                long lon3 = new Integer(arr[n-1]).longValue();
                System.out.println(lon1*lon2*lon3);
            }
        }else if(arr[0] < 0 && arr[1] > 0){
            long lon1 = new Integer(arr[n-3]).longValue();
            long lon2 = new Integer(arr[n-2]).longValue();
            long lon3 = new Integer(arr[n-1]).longValue();
            System.out.println(lon1*lon2*lon3);
        }else if(arr[0] < 0 && arr[n-1] < 0){
            long lon1 = new Integer(arr[n-3]).longValue();
            long lon2 = new Integer(arr[n-2]).longValue();
            long lon3 = new Integer(arr[n-1]).longValue();
            System.out.println(lon1*lon2*lon3);
        }else{
            long lon1 = new Integer(arr[n-3]).longValue();
            long lon2 = new Integer(arr[n-2]).longValue();
            long lon3 = new Integer(arr[n-1]).longValue();
            System.out.println(lon1*lon2*lon3);
        }
    }
}

啊啊啊  我综合想了一下,最后分情况解决的。看着比较复杂,其实把所有情况考虑进来之后就能理解了。而且有些情况可以合并。但是我没有合并。
发表于 2019-05-24 13:43:20 回复(0)
这种解法属于偷懒吗?
/*题解思路:先建立一个一维vector向量,for循环存要输入的数组A[n],使用sort对数组进行升序排序
分析可知,最大乘积出现在排序后数组的:
1、最后三个的乘积:n-1、n-2、n-3
2、最前面两个和最后一个的乘积:0、1、n-2
使用long long类型的目的就是三个数乘积后的结果可能会超出int或者long的存储范围,因为试过int,只能通过22%          */
#include<bits/stdc++.h>   //万能的C++头文件,包含了基本上用到的所有头文件
using namespace std;

int main()
{
    int n;
    cin>>n;  //输入数组大小n
    vector<long long> nums(n,0); //建立大小为n的vector数组,一定要这样写,否则会发生段错误(数组越界,堆栈溢出(比如,递归调用层数太多)等情况引起)
    for(int i = 0;i<n;i++)
    {
        cin>>nums[i];   //只有上面vector那样写了,这里才可以这样写
    }
    sort(num***egin(),nums.end());   //使用算法中的sort函数对数组进行升序排序
    long long temp1 = nums[0]*nums[1]*nums[n-1];     //前两个和最后一个相乘
    long long temp2 = nums[n-1]*nums[n-2]*nums[n-3];  //最后三个相乘
    if(temp1 >= temp2)
        cout<<temp1;
    else
        cout<<temp2;
    return 0;
}

编辑于 2019-05-21 17:12:22 回复(0)
/*
有没有好看又帅气的大佬帮我分析下代码,case通过率为22.22% 用例: 61  3472 -7098 -9281 7789 7955 6101 5051 7778 3090 7423 -7151 5652 1595 
-8094 677 -8324 8347 -2482 9313 -9338 -3157 8559 6945 3618 3087 121 -8468
 3225 1356 6939 2799 -7231 -6309 -5453 633 -8689 -4776 2714 -2743 -1409 5918
 -3333 1803 8330 -2206 -6117 -4486 -7903 -4375 -3739 2897 8056 -5864 -522 7451 
-4541 -2813 5790 -532 -6517 925  */ 

var n = parseInt(readline());
var arr = readline().split(' ');
if(n<3){
    console.log(false);
}
function num(a,b){
    a-b;
}
arr.sort(num);

var res=(arr[n-1]*arr[n-2]*arr[n-3]>arr[0]*arr[1]*arr[n-1])?arr[n-1]*arr[n-2]*arr[n-3]:arr[0]*arr[1]*arr[n-1];

console.log(res);

编辑于 2019-05-15 17:35:13 回复(2)
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
    Scanner scan=new Scanner(System.in);
    int n=scan.nextInt();
    long []array=new long[n];
    for(int i=0;i<n;i++){
        long a=scan.nextLong();
        array[i]=a;
    }
    getmax(array);
}
    public static void getmax(long[] x){
        long spm=0;
        for(int j=0;j<x.length-1;j++){
for(int i=0;i<x.length-1-j;i++){
            if(x[i]!=0){
                if(x[i]<x[i+1]){
                    spm=x[i+1];
                    x[i+1]=x[i];
                    x[i]=spm;
                }
            }
      }
        }
        long min=x[x.length-1];
        long bigmin=x[x.length-2];
        long sum=Math.max(min*bigmin*x[0], x[0]*x[1]*x[2]);
        System.out.println(sum);
    }
        }
    
 





有没有人帮我看看我这个怎么只过了88%?????
发表于 2019-04-23 20:14:05 回复(0)
import java.util.Arrays;
import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String st = sc.nextLine();
        String[] st2 = st.split(" ");
        int []arr = new int[st2.length];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = Integer.parseInt(st2[i]);
        }
        Arrays.sort(arr);
        int max1 = arr[arr.length-1]*arr[0]*arr[1];
        int max2 = arr[arr.length-1]*arr[arr.length-2]*arr[arr.length-3];
        int max;
        if(max1>max2) {
            max = max1;
        }else {
            max = max2;
        }
        System.out.println(max);
}
    }


有没有大神帮看看这个为啥case通过率是0呢
编辑于 2019-04-10 16:02:34 回复(1)
# 看了很多解答不够严谨,没有考虑到全是负数的情况,当全是负数的时候需要找负数中最大的三个。首先认为输入肯定大于三个数,其次再存最大的三个正数、负数、最小的两个负数,我还存了一个是否有0的flag,这个可以没有,需要的应该有8个数


import math
N = int(input())
A = [int(x) for x in input().split()]

if len(A) == 3:
    print(A[0] * A[1] * A[2])
else:
    max_A = [0,0,0]
    zero = False
    max_A_negative = [-math.inf,-math.inf,-math.inf]
    min_A_negative = [0,0]
    for a in A:
        if a == 0:
            zero = True
        if a > 0:
            if a <= max_A[0]:
                continue
            if a > max_A[0]:
                max_A[0] = a
                max_A = sorted(max_A)
        if a < 0:
            if a >= min_A_negative[0]:
                pass
            else:
                min_A_negative[0] = a
                min_A_negative = sorted(min_A_negative, reverse=True)
            if a <= max_A_negative[0]:
                pass
            else:
                max_A_negative[0] = a
                max_A_negative = sorted(max_A_negative)
    
    if max_A[-1] == 0:  # 全是负数或0
        if zero:
            print(0)
        else:
            print(max_A_negative[0] * max_A_negative[1] * max_A_negative[2])
    else:   # 有正数
        
        print(max(max_A[2] * max_A[1] * max_A[0], min_A_negative[1] * min_A_negative[0] * max_A[-1]))



发表于 2019-04-08 16:18:46 回复(0)