题解 | #最大乘积#

最大乘积

https://www.nowcoder.com/practice/4db8abc3ee814b338ebc37024d7e8b46

解题思路

这是一道求最大乘积的问题，主要思路如下：

最大乘积可能来自两种情况：
- 最大的三个正数相乘
- 最大的正数乘以最小的两个负数（如果存在）
需要维护的变量：
- $large1, large2, large3$ ：最大的三个数
- $small1, small2$ ：最小的两个数
一次遍历即可找到所需的数字，比较两种情况得到最终结果

代码

cpp
java
python

#include <climits>
#include <iostream>
using namespace std;
typedef long long ll;

int main() {
    ios_base::sync_with_stdio(false);
    ll N;
    cin >> N;
    
    // 初始化变量
    ll large1 = LLONG_MIN, large2 = LLONG_MIN, large3 = LLONG_MIN;
    ll small1 = LLONG_MAX, small2 = LLONG_MAX;
    
    // 一次遍历找出最大的三个数和最小的两个数
    for(ll i = 0; i < N; ++i) {
        ll num;
        cin >> num;
        
        // 更新最大的三个数
        if(num > large1) {
            large3 = large2;
            large2 = large1;
            large1 = num;
        } else if(num > large2) {
            large3 = large2;
            large2 = num;
        } else if(num > large3) {
            large3 = num;
        }
        
        // 更新最小的两个数
        if(num < small1) {
            small2 = small1;
            small1 = num;
        } else if(num < small2) {
            small2 = num;
        }
    }
    
    // 比较两种可能的结果
    cout << max(large1*large2*large3, large1*small1*small2) << endl;
    return 0;
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        
        // 初始化变量
        long large1 = Long.MIN_VALUE, large2 = Long.MIN_VALUE, large3 = Long.MIN_VALUE;
        long small1 = Long.MAX_VALUE, small2 = Long.MAX_VALUE;
        
        // 一次遍历找出最大的三个数和最小的两个数
        for(int i = 0; i < N; i++) {
            long num = sc.nextLong();
            
            // 更新最大的三个数
            if(num > large1) {
                large3 = large2;
                large2 = large1;
                large1 = num;
            } else if(num > large2) {
                large3 = large2;
                large2 = num;
            } else if(num > large3) {
                large3 = num;
            }
            
            // 更新最小的两个数
            if(num < small1) {
                small2 = small1;
                small1 = num;
            } else if(num < small2) {
                small2 = num;
            }
        }
        
        // 比较两种可能的结果
        System.out.println(Math.max(large1*large2*large3, large1*small1*small2));
    }
}

n = int(input())
nums = list(map(int, input().split()))

# 初始化变量
large1 = large2 = large3 = float('-inf')
small1 = small2 = float('inf')

# 一次遍历找出最大的三个数和最小的两个数
for num in nums:
    # 更新最大的三个数
    if num > large1:
        large3 = large2
        large2 = large1
        large1 = num
    elif num > large2:
        large3 = large2
        large2 = num
    elif num > large3:
        large3 = num
    
    # 更新最小的两个数
    if num < small1:
        small2 = small1
        small1 = num
    elif num < small2:
        small2 = num

# 比较两种可能的结果
print(max(large1*large2*large3, large1*small1*small2))