// 演算法與 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);
    }
};