最大乘积

#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)。

#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]))

//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]));
    }
}

#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;
}

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;
    }
}

#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;
}

//利用包装类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);

    }
}

//最大的三个和最小的两个--最大的三个相乘 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;
}

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));
    }
}

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]);

这种解法属于偷懒吗？

#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;
}

/*
有没有好看又帅气的大佬帮我分析下代码，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);

# 看了很多解答不够严谨，没有考虑到全是负数的情况，当全是负数的时候需要找负数中最大的三个。首先认为输入肯定大于三个数，其次再存最大的三个正数、负数、最小的两个负数，我还存了一个是否有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]))