[编程题]最大乘积
#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两行。
假装没有看到时间复杂度要求。。
题目有bug，根本没说第一行是输入数组的长度。误以为只有一行输入。
思路如下：
- 先对数组进行排序
- 如果全为负数或全为正数，取最后三个数相乘既为最大乘积。关键是既有正数又有负数的情况（0其实可以看作负数）。如果有两个正数(例如
[-2，-1，0，1，2])，那么最大值为arr[0] * arr[1] * arr[-1], 如果有一个正数(例如[-2，-1，0，2])，最大值同样为arr[0] * arr[1] * arr[-1]。 - 结合上面两种情况，只需要取
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;///拼多多#if1intmain(){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)
//自我感觉这么做最简单
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);}
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)
问题信息
通过挑战的用户
查看代码-
2021-03-07 18:26:24 -
2021-03-07 13:53:36
-
2021-03-05 21:46:48
-
2021-03-05 20:49:22
-
2021-03-03 21:52:37
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客网公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802(电话) admin@nowcoder.com
- 牛客科技© All rights reserved
- 京ICP备14055008号-4 增值电信业务经营许可证
-
京公网安备 11010502036488号
