首页 > 试题广场 > 最大乘积
[编程题]最大乘积
  • 热度指数:111516 时间限制: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<stdio.h>
/*C语言 找到最大的三个正数,最小的两个负数*/
int main()
{
    int length,i;
    scanf("%d",&length);
    long min1=1,min2=1;
    long max1=1,max2=1,max3=1;
    long value,max_product=-1;
    for(i=0;i<length;i++)
    {
        scanf("%ld",&value);
        if(value>max1){max3 = max2;max2 = max1;max1 = value;}
        else if(value>max2){max3 = max2;max2 = value;}
        else if(value>max3)max3 = value;
        else if(value<min1){min2 = min1;min1 = value;}
        else if(value<min2)min2 = value;
    }
    if(max2+max3>-min1-min2)max_product=max1*max2*max3;    else max_product=min1*min2*max1;
    printf("%ld\n",max_product);
    return 0;
}


编辑于 2019-05-13 10:50:47 回复(0)

看大家代码都很长来个短一点的
基本思路: 用选择排序的思路找到最大的3个数和最小的3个数 时间复杂度O(6n)
最大乘积只有三种情况
1.最大的三个数相乘
2.最小的三个数相乘(全是负数的情况) ,
3.最小的两个负数再乘以最大的正数
从这三种中取最大的即可
循环加数组尽量简化代码

#include<iostream>
#include<algorithm>
using namespace std;

const int maxn = 1e6;
long long arr[maxn];

int main(){
    int n;
    long long maxi[3], mini[3], ans;
    cin>>n;
    for(int i = 0; i < n; i++) scanf("%lld", &arr[i]);
    for(int i = 0; i < 3; i++){
        for(int j = i + 1; j < n; j++) if(arr[j] > arr[i]) swap(arr[j], arr[i]);
        maxi[i] = arr[i];
    }
    for(int i = 0; i < 3; i++){
        for(int j = i + 1; j < n; j++) if(arr[j] < arr[i]) swap(arr[j], arr[i]);
        mini[i] = arr[i];
    }
    ans = max(maxi[0]*maxi[1]*maxi[2], 
              max(maxi[0]*mini[0]*mini[1], mini[0]*mini[1]*mini[2]));
    printf("%lld\n", ans);
}
发表于 2019-01-12 11:44:14 回复(15)
/*定义五个数,一个最大,一个次大,一个第三大,一个最小,一个次小。
只要找到这五个数,问题就解决了。因为最大乘积只可能是
最大*(次大*第三大) 或者是 最大*(最小*次小)。时间复杂度O(n),
空间复杂度O(1)。PS:这道题输入有问题,题目给的样例是直接给了一组数,
而此时用例先给了一个数的个数n,然后再给了一组数*/
#include<iostream>
#include<limits.h>
using namespace std;
int main()
{
    long long min_fir=INT_MAX,min_sec=INT_MAX;
    long long max_fir=INT_MIN,max_sec=INT_MIN,max_third=INT_MIN;
    int n,num;
    long long mul;
    cin>>n;
    for(int i=0;i<n;i++)
    {
         cin>>num;
         if(num<min_fir)
            {
                min_sec = min_fir;
                min_fir = num;
            }
            else if(num<min_sec)
                min_sec = num;
            if(num>max_fir)
            {
                max_third = max_sec;
                max_sec = max_fir;
                max_fir = num;
            }
            else if(num>max_sec)
            {
                max_third = max_sec;
                max_sec = num;
            }
            else if(num>max_third)
                max_third = num;
    }
    mul = max_fir*max_sec*max_third > max_fir*min_fir*min_sec ? max_fir*max_sec*max_third : max_fir*min_fir*min_sec;
    cout<<mul<<endl;
    return 0;
}

发表于 2018-04-02 21:58:36 回复(35)
//AC的o(n)代码,一定要注意存储的数组类型是long型(之前是int型就没通过)
//在遍历数组是需要记录第一,第二,第三大,和最小,次小的数(负负的正)
// 返回Math.max(max1*max2*max3,max1*min1*min2) 

import java.util.Arrays;
import java.util.Scanner;

public class PinDuoDuo1 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        long[] array = new long[n];
        for (int i = 0; i <n ; i++) {
            array[i] = sc.nextLong();
        }
        getLargestMul(array,n);
    }
    static void getLargestMul(long[] num, int len){
        long max1=0,max2=0,max3=0, min1=0,min2=0;
        for (int i = 0; i <len ; i++) {
            if(num[i]!=0){
                if(num[i]>max1){
                    max3 = max2;
                    max2 = max1;
                    max1 = num[i];
                }else if(num[i]>max2){
                    max3 = max2;
                    max2 = num[i];
                }else if(num[i]>max3){
                    max3 = num[i];
                }else if(num[i]<min1 ){
                    min2 = min1;
                    min1 = num[i];
                }else if(num[i]>min1 && num[i]<min2){
                    min2 = num[i];
                }
            }else continue;

        }
        long max = Math.max(max1*max2*max3,max1*min1*min2);
        System.out.println(max);
    }
} 
编辑于 2017-08-07 10:30:15 回复(30)
#include<iostream>
#include<limits.h>
using namespace std;
int main()
{
    int i, n, num;
    long long max_mul;
    /* max1, max2, max3 分别为最大值,次大值,第三大值
     * min1, min2 分别为最小值,次小值
    */
    long long max1, max2, max3, min1, min2;
    max1 = max2 = max3 = INT_MIN;
    min1 = min2 = INT_MAX;
    cin >> n;
    for(i = 0; i < n; i++)
    {
        cin >> num;
        if(num < min1)
        {
            min2 = min1;
            min1 = num;
        }
        else if(num < min2)
        {
            min2 = num;
        }
        
        if(num > max1)
        {
            max3 = max2;
            max2 = max1;
            max1 = num;
        }
        else if(num > max2)
        {
            max3 = max2;
            max2 = num;
        }
        else if(num > max3)
        {
            max3 = num;
        }
    }
    max_mul = max1*max2*max3 > max1*min1*min2 ? max1*max2*max3 : max1*min1*min2;
    cout << max_mul << endl;
    return 0;
} 

编辑于 2019-02-26 23:51:51 回复(2)
import java.util.Scanner;

public class Main{
    
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        long[] array=new long[n];
        for(int i=0;i<n;i++){
            array[i]=sc.nextLong();
        }

        getTheMostValue(array,n);
    }
    
    public static void getTheMostValue(long[] num,int len){
        long max1=0;long max2=0;long max3=0;long min1=0;long min2=0;
        
        for(int i=0;i<len;i++){
            if(num[i]>max1){
                max3=max2;
                max2=max1;
                max1=num[i];
            }else if(num[i]>max2){
                max3=max2;
                max2=num[i];
            }else if(num[i]>max3){
                max3=num[i];
            }else if(num[i]<min1){
                min2=min1;
                min1=num[i];
            }else if(num[i]>min1&&num[i]<min2){
                min2=num[i];
            }
        }
        
        long max=Math.max(max1*max2*max3,max1*min1*min2);
        System.out.println(max);
    }
}

发表于 2019-04-21 21:58:24 回复(0)

python两行。

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

  2. 题目有bug,根本没说第一行是输入数组的长度。误以为只有一行输入。


思路如下:

  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:50:55 回复(16)
//笔试时候由于把类型写错了 ,编译只能通过22.22%,把类型改了一下,可以通过了
//思路:先统计一下输入的所有数中,零的个数、>0的个数、<0的个数
//然后枚举各种情况,确定一种情况,然后扫描整个数组两遍就行了
#include <iostream>
using namespace std;
///拼多多
#if1
intmain()
{
    intn;
    cin >> n;
    int*arr = newint[n];
    for(inti = 0; i < n; i++)
    {
        cin >> arr[i];
    }
    longlongposnum = 0;
    longlongminnum = 0;
    longlongzeronum = 0;
    longlongres;
    for(inti = 0; i < n; i++)
    {
        if(arr[i]>0)
        {
            posnum++;
        }
        elseif(arr[i]<0)
        {
            minnum++;
        }
        else
        {
            zeronum++;
        }
    }
    if(posnum == 0&& minnum == 0)
    {
        res = 0;
    }
    elseif(minnum == 0)
    {
        if(posnum - zeronum < 3)
        {
            res = 0;
        }
        else
        {
            longlongmax = 0;
            longlongmid = 0;
            longlongmin = 0;
            longlongmax_index = -1;
            longlongmid_index = -1;
            longlongmin_index = -1;
            for(inti = 0; i < n; i++)
            {
                if(arr[i] >= max)
                {
                    max = arr[i];
                    max_index = i;
                }
            }
            for(inti = 0; i < n; i++)
            {
                if(i == max_index)
                {
                    continue;
                }
                if(arr[i] >= mid&&arr[i] <= max)
                {
                    mid = arr[i];
                    mid_index = i;
                }
            }
            for(inti = 0; i < n; i++)
            {
                if(i == max_index || i == mid_index)
                {
                    continue;
                }
                if(arr[i] >= min && arr[i] <= mid && arr[i] <= max)
                {
                    min = arr[i];
                    min_index = i;
                }
            }
            res = max*mid*min;
        }
    }
    elseif(posnum == 0)
    {
        if(minnum - zeronum < 3)
        {
            res = 0;
        }
        else
        {
            longlongmax = 0x80000000;
            longlongmid = 0x80000000;
            longlongmin = 0x80000000;
            longlongmax_index = -1;
            longlongmid_index = -1;
            longlongmin_index = -1;
            for(inti = 0; i < n; i++)
            {
                if(arr[i] >= max)
                {
                    max = arr[i];
                    max_index = i;
                }
            }
            for(inti = 0; i < n; i++)
            {
                if(i == max_index)
                {
                    continue;
                }
                if(arr[i] >= mid&&arr[i] <= max)
                {
                    mid = arr[i];
                    mid_index = i;
                }
            }
            for(inti = 0; i < n; i++)
            {
                if(i == max_index || i == mid_index)
                {
                    continue;
                }
                if(arr[i] >= min && arr[i] <= mid && arr[i] <= max)
                {
                    min = arr[i];
                    min_index = i;
                }
            }
            res = max*mid*min;
        }
    }
    else
    {
        longlongmin_num = 0;
        longlongmin_max = -1;
        longlongmin_max_index = -1;
        longlongmin_sec = -1;
        longlongmin_sec_index = -1;
        longlongtmp = 0;
        for(inti = 0; i < n; i++)
        {
            if(arr[i] < 0)
            {
                min_num++;
                if(min_max >= arr[i])
                {
                    min_max = arr[i];
                    min_max_index = i;
                }
            }
            /*else
            {
            posnum++;
            }*/
        }
        if(min_num >= 2)
        {
            for(inti = 0; i < n; i++)
            {
                if(arr[i] < 0)
                {
                    if(min_sec >= arr[i] && min_sec >= min_max&&min_max_index != i)
                    {
                        min_sec = arr[i];
                        min_sec_index = i;
                    }
                }
            }
            intthird = 0;
            for(inti = 0; i < n; i++)
            {
                if(arr[i]>0&& arr[i] > third)
                {
                    third = arr[i];
                }
            }
            tmp = min_sec*min_max*third;
        }
        longlongpos_num = 0;
        longlongmax_max = -1;
        longlongmax_max_index = -1;
        longlongmax_sec = -1;
        longlongmax_sec_index = -1;
        longlongtmp1 = 0;
        for(inti = 0; i < n; i++)
        {
            if(arr[i] > 0)
            {
                pos_num++;
                if(max_max <= arr[i])
                {
                    max_max = arr[i];
                    max_max_index = i;
                }
            }
        }
 
 
 
        if(pos_num >= 2)
        {
            for(inti = 0; i < n; i++)
            {
                if(arr[i] > 0)
                {
                    if(max_sec <= arr[i] && arr[i] <= max_max&&max_max_index != i)
                    {
                        max_sec = arr[i];
                        max_sec_index = i;
                    }
                }
            }
            intthird1 = 0;
            for(inti = 0; i < n; i++)
            {
                if(arr[i]>0&& arr[i] > third1 && i != max_max_index && i != max_sec_index)
                {
                    third1 = arr[i];
                }
            }
            tmp1 = max_sec*max_max*third1;
        }
        if(tmp >= tmp1)
        {
            res = tmp;
        }
        else
        {
            res = tmp1;
        }
    }
    cout << res << endl;
    return0;
}
#endif

发表于 2017-08-07 00:26:15 回复(13)
#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)
 import java.util.*;
public class Main{
    public static void main(String[] args)
    {
        Scanner sc=new Scanner(System.in);
        long J1=0,J2=0,J=0;
        while(sc.hasNext())
        {
            int N=sc.nextInt();
            long n []=new long [N];
            for(int i=0;i<N;i++)
            {
                n[i]=sc.nextLong();
            }
            Arrays.sort(n);//排序
            J1=n[N-1]*n[N-2]*n[N-3];//要么最后三个正数最大
            J2=n[0]*n[1]*n[N-1];//要么前两个负数加上最后一个正数乘积最大 负负得正  两负一正得正
            if(J1>=J2){ J=J1;}//比较这两个乘积
            else{J=J2;}
              System.out.println(J);
        }
      
    }
}
发表于 2019-04-04 09:24:28 回复(0)
#include<iostream>
#include<algorithm>
#include<limits.h>
using namespace std;
int main(){
    int n;
    cin>>n;
    vector<long long>nums(n);
    for(int i=0;i<n;i++){
        cin>>nums[i];
    }
    long long max1=1,max2=1,max3=1,min1=1,min2=1;
    for(int i=0;i<n;i++){
        if(nums[i]>max1){
           max3=max2;
           max2=max1;
           max1=nums[i];
        }
        else if(nums[i]>max2){
           max3=max2;
           max2=nums[i];
        }
        else if(nums[i]>max3){
           max3=nums[i];
        }
        else if(nums[i]<min1){
           min2=min1;
           min1=nums[i];
        }
        else if(nums[i]<min2){
           min2=nums[i];
        }
    }
    long long result1,result2,result;
    result1=max1*max2*max3;
    result2=max1*min1*min2;
    result=max(result1,result2);
    cout<<result<<endl;
    return 0;
}

发表于 2017-08-09 16:23:54 回复(3)
#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)