// 演算法：最大乘積必為「三個最大數的乘積」或「兩個最小數×最大數的乘積」二選一。
// 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;
}