628. Maximum Product of Three Numbers

題目 / Problem

中文： 給定一個整數陣列 nums，從中挑出三個數字，使它們的乘積最大，回傳這個最大乘積。

English: Given an integer array nums, pick three numbers whose product is the maximum possible, and return that maximum product.

限制 / Constraints: - 3 <= nums.length <= 10^4（陣列至少有 3 個元素 / at least three elements） - -1000 <= nums[i] <= 1000（每個元素介於 -1000 到 1000 之間，可能是負數 / values can be negative）

範例 / Worked example:

Input:  nums = [-4, -3, 1, 2, 5]
Output: 60

解釋：最大乘積來自兩個最小的負數 -4 * -3 = 12，再乘上最大的正數 5，得到 12 * 5 = 60。這比三個最大正數 1 * 2 * 5 = 10 還要大。 Explanation: the best product comes from the two most-negative numbers -4 * -3 = 12 times the largest positive 5, giving 60 — larger than the three biggest positives 1 * 2 * 5 = 10.

名詞解釋 / Glossary

• 陣列 / array：一段連續排列、可用索引（index，從 0 開始）存取的資料，例如 nums[0] 是第一個元素。/ A sequence of values you access by a 0-based index, e.g. nums[0] is the first element.
• 乘積 / product：把數字相乘的結果，例如 2 * 3 = 6。/ The result of multiplying numbers together.
• 負負得正 / negative times negative is positive：兩個負數相乘會變成正數，例如 (-4) * (-3) = 12。這是本題的關鍵。/ Multiplying two negatives yields a positive — the crux of this problem.
• 排序 / sorting：把陣列由小到大（升序）重新排列。排序後最小值在開頭、最大值在結尾。/ Rearranging the array from smallest to largest so extremes sit at the two ends.
• 時間複雜度 / time complexity：用 O(...) 表示演算法隨資料量 n 成長時所需步數的粗略量級。/ A rough measure O(...) of how the number of steps grows with input size n.
• 一次掃描 / single pass：只從頭到尾走訪陣列一遍就得到答案，不需重複遍歷。/ Solving by walking through the array only once.

思路

最直覺的暴力法是列舉所有三個數字的組合，各自算乘積再取最大值。但三重迴圈的複雜度是 O(n³)，當 n 高達 10⁴ 時大約要 10¹² 次運算，會嚴重超時。關鍵觀察是：能組成最大乘積的數字，一定落在「排序後的兩端」。因為數值有正有負，答案只會是兩種情況之一：其一是三個最大的數相乘（當它們都是正數或整體偏正時最有利）；其二是兩個最小的數（也就是兩個最負的數，負負得正變成很大的正值）再乘上最大的那個數。我們不知道哪一種勝出，所以兩種都算，取較大者。實作上有兩條路：把陣列排序後直接取 nums[n-1]*nums[n-2]*nums[n-3] 與 nums[0]*nums[1]*nums[n-1] 比較，這需要 O(n log n)；更好的做法是一次掃描找出「最大的三個數」和「最小的兩個數」這五個值，就足以覆蓋兩種情況，只要 O(n) 時間與 O(1) 空間。

The brute-force idea is to try every triple and keep the biggest product, but a triple loop is O(n³) — with n up to 10⁴ that's ~10¹² operations and will time out. The key insight is that the numbers forming the maximum product must live at the two extremes of the sorted order. Because values can be negative, the answer is one of only two candidates: the product of the three largest numbers, or the product of the two smallest (most negative) numbers times the single largest number — since two negatives multiply into a big positive. We can't know in advance which wins, so we compute both and take the max. You can either sort and read off the ends in O(n log n), or — better — make one linear pass tracking just five quantities: the three largest values and the two smallest values. Those five cover both candidates, giving an O(n) time, O(1) space solution.

逐步走查 / Walkthrough

以第一個範例 nums = [1, 2, 3] 用「一次掃描」演算法追蹤五個變數。/ Tracing the single-pass algorithm on nums = [1, 2, 3].

我們維護：max1 ≥ max2 ≥ max3（最大三個）與 min1 ≤ min2（最小兩個）。初始時最大值設為極小、最小值設為極大。/ We keep max1 ≥ max2 ≥ max3 (top three) and min1 ≤ min2 (bottom two), initialized to extremes.

最後計算兩個候選 / final two candidates: - 三個最大：max1*max2*max3 = 3*2*1 = 6 - 兩最小 × 最大：min1*min2*max1 = 1*2*3 = 6

取較大者 → max(6, 6) = 6，即答案。/ Take the larger → 6, the expected output.

Solution — C

// 演算法：最大乘積必為「三個最大數的乘積」或「兩個最小數×最大數的乘積」二選一。
// Algorithm: the max product is either the three largest numbers, or the two
// smallest (most-negative) numbers times the single largest number.
// 一次掃描追蹤這五個值，時間 O(n)、空間 O(1)。
// One pass tracks those five values — O(n) time, O(1) space.

#include <limits.h>   // 提供 INT_MAX / INT_MIN 常數 / gives INT_MAX and INT_MIN

int maximumProduct(int* nums, int numsSize) {
    // 最大的三個數，初始設為「最小可能整數」，任何真實值都能取代它。
    // Three largest values; start at INT_MIN so any real number replaces them.
    int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;

    // 最小的兩個數，初始設為「最大可能整數」，任何真實值都能取代它。
    // Two smallest values; start at INT_MAX so any real number replaces them.
    int min1 = INT_MAX, min2 = INT_MAX;

    // 只走訪陣列一次 / walk the array exactly once
    for (int i = 0; i < numsSize; i++) {
        int x = nums[i];  // 取出目前元素 / current element (array indexing)

        // 更新最大三個：若 x 比 max1 大，x 成為新第一，舊值往下遞移，避免資料遺失。
        // Update top three: if x beats max1, x becomes 1st and old values shift down.
        if (x >= max1) {
            max3 = max2;   // 舊第二變第三 / old 2nd becomes 3rd
            max2 = max1;   // 舊第一變第二 / old 1st becomes 2nd
            max1 = x;      // x 成為新第一 / x is the new 1st
        } else if (x >= max2) {
            max3 = max2;   // 只需下移一層 / x sits between max1 and max2
            max2 = x;
        } else if (x >= max3) {
            max3 = x;      // x 只夠當第三大 / x is only the 3rd largest
        }

        // 更新最小兩個：邏輯與上面對稱，方向相反。
        // Update bottom two: symmetric logic, opposite direction.
        if (x <= min1) {
            min2 = min1;   // 舊最小變第二小 / old smallest becomes 2nd smallest
            min1 = x;      // x 成為新最小 / x is the new smallest
        } else if (x <= min2) {
            min2 = x;      // x 只夠當第二小 / x is only the 2nd smallest
        }
    }

    // 候選一：三個最大數的乘積 / candidate 1: product of three largest
    int candA = max1 * max2 * max3;

    // 候選二：兩個最小數（可能是負數）× 最大數 / candidate 2: two smallest × largest
    int candB = min1 * min2 * max1;

    // 回傳兩個候選中較大者 / return the larger of the two candidates
    return candA > candB ? candA : candB;
}

Solution — C++

// 演算法與 C 版相同：答案是「三最大數乘積」或「兩最小數×最大數」二者取大。
// Same algorithm as the C version: max product is either the three largest, or
// the two smallest (most-negative) times the largest.
// 這裡示範最簡潔的排序寫法，讀者更易看懂端點的意義；O(n log n) 時間、O(1) 額外空間。
// Here we show the concise sort-based version so the "two extremes" idea is obvious;
// O(n log n) time, O(1) extra space.

#include <vector>      // std::vector 動態陣列 / dynamic array container
#include <algorithm>   // std::sort 與 std::max / sorting and max helpers

class Solution {
public:
    int maximumProduct(std::vector<int>& nums) {
        // 由小到大排序：排序後最小值在最前、最大值在最後。
        // Sort ascending so the smallest values land at the front, largest at the back.
        std::sort(nums.begin(), nums.end());

        int n = nums.size();  // 元素個數 / number of elements

        // 候選一：最後三個（最大的三個）相乘 / candidate 1: last three (largest) multiplied
        int candA = nums[n - 1] * nums[n - 2] * nums[n - 3];

        // 候選二：最前兩個（最小/最負）× 最後一個（最大） / candidate 2: first two × last one
        int candB = nums[0] * nums[1] * nums[n - 1];

        // std::max 直接回傳兩者中較大者 / std::max returns the larger of the two
        return std::max(candA, candB);
    }
};

複雜度 / Complexity

• Time（一次掃描版 / single-pass C）： O(n) — 只遍歷陣列一次，每個元素做常數次比較；n 是陣列長度，主導成本就是這唯一的迴圈。/ One pass, constant work per element; n is the array length and the single loop dominates.
• Time（排序版 / sort-based C++）： O(n log n) — 成本由 std::sort 主導，比較次數與 n log n 成正比。/ Dominated by std::sort, whose comparisons scale as n log n.
• Space： O(1) — 兩種寫法都只用固定數量的變數，排序為原地進行，不隨 n 增加額外記憶體。/ Both use a fixed number of variables; the sort is in-place, so memory does not grow with n.

Pitfalls & Edge Cases

• 忘記負數 / forgetting negatives：只取「三個最大數」是最常見的錯誤。像 [-4,-3,1,2,5] 的答案 60 來自兩個負數相乘，漏掉候選二會答錯。程式同時計算兩個候選就避免了這個陷阱。/ Taking only the three largest is the classic bug; the two-negatives case (candB) must also be checked.
• 全負數 / all negatives：例如 [-1,-2,-3]，唯一組合是 -1*-2*-3 = -6（負數）。候選一 max1*max2*max3 正好處理這種情況，回傳最大（最接近 0）的負乘積。/ For all-negative input the answer is negative; candA correctly yields the least-negative product.
• 整數溢位 / integer overflow：三個值最大約 1000*1000*1000 = 10^9，仍在 32 位元 int（上限約 2.1×10⁹）範圍內，本題不會溢位；但若題目上限更大就需改用 long long。/ Product peaks near 10⁹, safely inside 32-bit int; larger bounds would require long long.
• 相等值的更新順序 / update order on ties：C 版用 >= 與 <= 並小心地先下移舊值再寫入新值，確保重複數字（如 [2,2,2]）也能正確填滿三個槽位。/ Using >=/<= and shifting old values before overwriting keeps duplicates like [2,2,2] correct.
• 初始值方向 / initializing extremes：找最大值要從 INT_MIN 起、找最小值要從 INT_MAX 起；若方向相反，第一個元素永遠無法取代初始值。/ Seed maxima with INT_MIN and minima with INT_MAX, or the first element can never replace them.