首页 > 试题广场 >

最大乘积

[编程题]最大乘积
  • 热度指数：119926 时间限制：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
算法知识视频讲解
添加回答
Python
一直都可以啊头像 一直都可以啊
import sys
def coremax(n,nums):
    max1,max2,max3= -sys.maxsize - 1, -sys.maxsize - 1, -sys.maxsize - 1
    min1,min2=sys.maxsize, sys.maxsize
    ans=0
    for i in range(n):
        if nums[i]>max1:
            max3=max2
            max2=max1
            max1=nums[i]
        elif nums[i]>max2:
            max3=max2
            max2=nums[i]
        elif nums[i]>max3:
            max3=nums[i]
        if nums[i]<min1:
            min2=min1
            min1=nums[i]
        elif nums[i]<min2:
            min2=nums[i]
    ans=max(max1*max2*max3,max1*min1*min2)
    return ans
n=int(input())
nums=list(map(int,input().split()))
res=coremax(n,nums)
print(res)
发表于 2020-08-03 20:57:52 回复(0)
Python
哈哈～柳暗花明头像 哈哈～柳暗花明

第一次写python,大部分时间花在看语法上了，本来想着删除0，结果莫名就过去了 

n = int(input())
listt = list(map(lambda x:int(x), input().split()))
listt.sort()

if len(listt) == 3:
    print(listt[0] * listt [1] * listt[2])
elif len(listt) >= 3:
        max = listt[-2]*listt[-3]
        if max < listt[0]*listt[1]:
            max = listt[1]*listt[0]
        print(listt[-1]*max)
编辑于 2019-12-23 23:35:18 回复(0)
Python
(≧∇≦)三玖头像 (≧∇≦)三玖 
# 方法一
def pri(m,a):
    if m<3:
        return 0
    result_p = [0,0,0]  # 正数
    result_n = [0,0,0]  # 负数
    num_0 = 0
    for i in a:
        if i>result_p[0]:  # 正数前3或包括0的前三大
            result_p[0]=i
            result_p.sort()
        if i<0:  # 负数前3或包括0的前三小
            if result_n[-1]==0:
                result_n[-1]=i
                result_n.sort()
            elif i<result_n[-1]:
                result_n[-1]=i
                result_n.sort()
        if i==0:
            num_0 += 1
    while result_p[0]==0:  # 删除正数列表中的0项
        del result_p[0]
        if not result_p:  # 如果都是0，删除完了
            break
    while result_n[-1]==0:  # 删除负数列表中的0项
        del result_n[-1]
        if not result_n:  # 如果都是0，删除完了
            break
    if num_0>0:
        result_0 = [0,0,0]  # 如果0超级多不至于占内存，用一个0的话return中可能溢出指针
    else:
        result_0 = []
    result = result_n+result_0+result_p
    return max(result[0]*result[1]*result[-1],result[-3]*result[-2]*result[-1])
m = int(input())
a = list(map(int,input().split(' ')))
print(pri(m,a))
感觉应该考虑挺全的，个人愚见 
#方法二 分别求出max1，max2，max3，min2，min1
def pri(m,a):
    if m<3:
        return 0
    def get_max(b):
        max_ = b[0]
        max_index = 0
        for i in range(len(b)):
            if b[i]>max_:
                max_ = b[i]
                max_index = i
        return max_,max_index
    def get_min(b):
        min_ = b[0]
        min_index = 0
        for i in range(len(b)):
            if b[i]<min_:
                min_ = b[i]
                min_index = i
        return min_,min_index
    max1,max_index = get_max(a)
    del a[max_index]
    max2,max_index = get_max(a)
    del a[max_index]
    max3,max_index = get_max(a)
    a.extend([max1,max2])
    min1,min_index = get_min(a)
    del a[min_index]
    min2,min_index = get_min(a)
    return max(min1*min2*max1,max1*max2*max3)
m = int(input())
a = list(map(int,input().split(' ')))
print(pri(m,a))


编辑于 2019-09-13 16:19:50 回复(0)
Python
白色纯度头像 白色纯度
不要偷懒，按照题目意思，时间复杂度O(n),空间复杂度O(1). 所以就用一个长度为3的最小栈模拟最大堆来存储最小的三个数，用一个长度为3的最大栈模拟最小堆来存储最大的三个数。我的代码小小的偷了懒，用了sort，但是绝对是符合题意的。时间复杂度3*n左右，空间复杂度就是长度为3的两个数组。 
def method(num):
    min_s = []
    max_s = []
    for i in num:
        if i<=0:
            if not min_s or len(min_s)<3:
                min_s.append(i)
                min_s.sort()
            elif i<min_s[-1]:
                k = len(min_s)
                while k>0 and i<min_s[k-1]:
                    k-=1
                    min_s[k] = min_s[k-1]
                min_s[k] = i
        else:
            if not max_s or len(max_s)<3:
                max_s.append(i)
                max_s.sort(reverse=True)
            elif i>max_s[-1]:
                w = len(max_s)
                while w>0 and i>max_s[w-1]:
                    w -= 1
                    max_s[w] = max_s[w-1]
                max_s[w] = i
    new = min_s + max_s[::-1]
    #print(new,min_s,max_s)
    return max(new[0]*new[1]*new[-1],new[-1]*new[-2]*new[-3])
if __name__=='__main__':
    n = int(input().strip())
    num = list(map(int,input().split()))
    print(method(num))


发表于 2019-09-02 17:18:34 回复(0)
Python
至死不渝201904102144416头像 至死不渝201904102144416 
n=input()
n=list(map(int,input().split()))
n.sort()
print(max(n[0]*n[1]*n[-1],n[-1]*n[-2]*n[-3]))

这里题有问题，必须在第一行加个n才能运行。
三个最大的数，无非有几种情况，绝对值最大的三个数

  1. 都是正数，那么取排序后的后三个数即可
  2. 有一个负数，两个正数，那么做法同上。
  3. 有两个负数，那么取排序后最小的两个数再乘以排序后最大的数。
  4. 有三个负数，此时取最大的正数即可。

因此所有的情况都只有两种算法：排序后的最大三个数相乘或者排序后的最小两个数相乘再乘以最大的数。

发表于 2019-07-18 19:22:49 回复(0)
Python
Evan_Han头像 Evan_Han
站在巨人的肩膀上--思路：分三种情况
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)
Python
风明瑾辰头像 风明瑾辰
n=int(input())
l=list(map(int,input().split()))
def max_l(l,n):
    if n<3:
        return None
    if n==3:
        return l[0]*l[1]*l[2]
    l.sort()
    maxNum=max(l[-1]*l[-2]*l[-3],l[0]*l[1]*l[-1])
    return maxNum
print(max_l(l,n))

发表于 2019-06-23 15:28:57 回复(0)
Python
SuperepuS头像 SuperepuS
n = int(input())
li = list(map(int,input().strip().split()))
def maxMulti(li,n):
    if n <= 2:
        return None
    else:
        li0 = li.copy()
        max1 = max(li)
        li.remove(max1)
        max2 = max(li)
        li.remove(max2)
        max3 = max(li)
        min1 = min(li0)
        li0.remove(min1)
        min2 = min(li0)
        m1 = max1 * max2 * max3
        m2 = max1 * min1 * min2
        if m1 >= m2:
            return m1
        else:
            return m2
print(maxMulti(li,n))
发表于 2019-05-15 14:36:29 回复(0)
Python
了不起的托马斯头像 了不起的托马斯
1、题目没有表述清楚，实际输入有两行，第一行是数字的个数，第二行是具体的数
例：
4
1 2 3 4
上面是输入样例
2、将第二行的数据按从小到大的顺序排序，最大的乘积要么是前两个乘以最后一个（考虑到有负数的情形），要么是最后三个相乘 
import sys
num = list()  # 用来存储数据
for i in range(2):
    a = sys.stdin.readline().strip().split()
    a = list(map(int, a))
    num.append(a)
num[1].sort()
d=num[1]
max_num=max(d[0]*d[1]*d[-1],d[-1]*d[-2]*d[-3])
print(max_num)

发表于 2019-04-29 19:59:10 回复(0)
Python
努力努力学习头像 努力努力学习
取三个数的最大值，思路是先把数组排序，用python的函数默认是从小到大，所以，前边的可能为负数，负负得正三负为负，取其二在用数组的负数去倒数的一个值，则可能为大，后三数全正的话，在正数中的乘积也是可能为最大，这两个相比较，得出最大的值 def maxshu(): i = input().split() A = [int(n) for n in input().split()] A = sorted(A) if len(A)>2: M1 = A[0]*A[1]*A[-1] M2 = A[-1]*A[-2]*A[-3] return max(M1,M2) if __name__ == '__main__': print(maxshu())
发表于 2019-04-20 20:56:17 回复(0)
Python
啊选.头像 啊选. 
n=eval(input().strip())
datas=list(map(int,input().strip().split()))
max1,max2,max3=[min(datas)]*3
min2,min1=[max(datas)]*2
for i in range(len(datas)):
    if datas[i]<min1:
        min2=min1
        min1=datas[i]
    elif datas[i]<min2:
        min2=datas[i]
    if datas[i]>max1:
        max3=max2
        max2=max1
        max1=datas[i]
    elif max2<datas[i]:
        max3=max2
        max2=datas[i]
    elif max3<datas[i]:
        max3=datas[i]
maxresult=max(max1*max2*max3,max1*min1*min2)
print(maxresult)

发表于 2019-04-12 01:15:15 回复(0)
Python
各位爸爸快赐我offer头像 各位爸爸快赐我offer 
n = int(input())
num = sorted(map(int, raw_input().split()))
print max(num[0]*num[1]*num[-1],num[-3]*num[-2]*num[-2])
好奇怪，同样的思路，python3能100%通过，python2只有88%的通过率。有大神能解释下吗😥
发表于 2019-04-07 11:09:32 回复(0)
Python
。。。。。。。。。111头像 。。。。。。。。。111
Array = input()
A = [int(x) for x in Array . split()]
A = sorted(A , reverse = True)
x = A[0] * A[1] * A[2]
y = A[0] * A[-1] * A[-2]
if x > y:
    print(x)
else:
    print(y)
请问我这个怎么通不过呀
发表于 2019-04-06 16:56:29 回复(0)
Python
蹲一大把的offer头像 蹲一大把的offer 
本题有缺陷：示例中不包含输入的数组长度，而测试代码中含有行数
思路：先拆分输入的数组，按从大到小的顺序排列，内置函数sort()
     考虑负数个数，内置函数len()
     如果没有负数或只有一个负数，最大乘积就是数列最后三位数的乘积
     如果有两个及以上的负数，最大乘积有两种可能：最小的两负数*最大的正数，最大的三个正数乘积，取最大值即可。




long = int(input(''))    #这里也未考虑输入的数组和输入的数组长度不符的现象，只需要加个报错就好
an = input("")    #输入数组
nums = []         #使用列表存储
for item in an.split(' '):    #拆分数组
    if '-' in item:    #如果是负数，则带有‘-’号
        nums.append(int(item.split('-')[1])*(-1))    #列表中存入整型
    else:              #正数及0
        nums.append(int(item))
nums.sort()        #升序排序
length_lose = len([item for item in nums if item<0])    #获取负数个数
multi = 1    #定义初始乘积为1
if length_lose<2:    #没有负数或只有一个负数     for item in nums[:-4:-1]:
        multi=multi*item
else:                #有两个及以上的负数     multi_1 = nums[0]*nums[1]*nums[-1]
    multi_2 = nums[-1]*nums[-2]*nums[-3]
    multi = max(multi_1,multi_2)
print(multi)


发表于 2019-03-28 20:53:46 回复(0)
Python
Re:煙花ゼロから易冷头像 Re:煙花ゼロから易冷 
n = int(input())#题目有BUG，根本没有给出第一行输入的是长度
A = list(map(int, input().split()))
A.sort()
print(max(A[-1]*A[-2]*A[-3], A[0]*A[1]*A[-1]))

发表于 2019-03-18 22:15:15 回复(0)
Python
海滩上种花头像 海滩上种花 
import sys
n=int(sys.stdin.readline().strip())
nums=sys.stdin.readline().strip()
nums=list(map(int, nums.split()))
#1.当数组的最大值<=0或者是数组的最小值>=0时,乘积最大就是数组中TOP3的乘积；
#2.除第一种情况外，就需要考虑数组中的最大的3个数和最小的2个数
max3=[]
min2=[]
for i in range(n):
    max3.sort()
    min2.sort()
    if len(max3)<3:
        max3.append(nums[i])
    elif nums[i]>max3[0]:
        max3[0]=nums[i]
    if len(min2)<2:
        min2.append(nums[i])
    elif nums[i]<min2[1]:
        min2[1]=nums[i]
max3.sort()
min2.sort()
a=max3[0]*max3[1]*max3[2]
b=min2[0]*min2[1]*max3[2]
max3mul=a if a>=b else b
#print(max3,min2)
print(str(max3mul))

发表于 2019-03-18 16:02:37 回复(0)
Python
我要扛offer回家头像 我要扛offer回家
n=int(input())
list=input()
a=sorted(map(int,list.split()))
print(max(a[-1]*a[-2]*a[-3],a[0]*a[1]*a[-1]))
发表于 2019-03-16 15:34:35 回复(0)
Python
givemefive201803242137745头像 givemefive201803242137745
l=list(map(int,input().strip().split()))
def max_value(arr):
    sort_list=sorted(list(arr),reverse=True)
    if len(sort_list)<3:
        return "please input 3 or more numbers"
    elif len(sort_list)==3:
        return sort_list[0]*sort_list[1]*sort_list[2]
    else:
        if sort_list[0]<0:
            return sort_list[-1]*sort_list[-2]*sort_list[-3]
        elif sort_list[-2]<0 and (sort_list[-1]*sort_list[-2]>sort_list[1]*sort_list[2]):
            return sort_list[0]*sort_list[-1]*sort_list[-2]
        else:
            return sort_list[0]*sort_list[1]*sort_list[2]
print(max_value(l))   
发表于 2019-03-13 20:19:12 回复(0)
Python
JCLI头像 JCLI

最关键的是：题目有两个输入，第一个是长度n（我用python，不用管），第二个才是数组输入。题目出错了。

发表于 2019-03-10 21:24:06 回复(0)
提交观点

问题信息

C++工程师 iOS工程师 安卓工程师 运维工程师 前端工程师 算法工程师 测试工程师 PHP工程师 贪心 模拟 2018 拼多多 Java工程师
来自：拼多多2018校招内推...
上传者：小小
难度：
26条回答 44476浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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