1464. Maximum Product of Two Elements in an Array

題目 / Problem

中文 給定一個整數陣列 nums，你需要選擇兩個不同的索引 i 和 j，回傳 (nums[i]-1)*(nums[j]-1) 的最大值。

English Given an integer array nums, choose two different indices i and j, and return the maximum value of (nums[i]-1)*(nums[j]-1).

限制 / Constraints - 2 <= nums.length <= 500 - 1 <= nums[i] <= 10^3

範例 / Example

Input:  nums = [3,4,5,2]
Output: 12

選 i=1（值 4）和 j=2（值 5）：(4-1)*(5-1) = 3*4 = 12。 Pick i=1 (value 4) and j=2 (value 5): (4-1)*(5-1) = 3*4 = 12.

名詞解釋 / Glossary

• 陣列 / Array：一段連續排列、可用索引（下標）存取的元素集合。nums[0] 是第一個元素。 / A contiguous, index-accessible sequence of values; nums[0] is the first element.
• 索引 / Index：元素在陣列中的位置編號，從 0 開始。 / The position number of an element, starting at 0.
• 暴力法 / Brute force：把所有可能的組合都試一遍，取最好的答案。簡單但可能慢。 / Try every possible combination and keep the best result — simple but potentially slow.
• 最大值與次大值 / Largest and second-largest：陣列中數值排第一大與第二大的兩個數。本題答案只跟這兩個有關。 / The top-two biggest numbers in the array; the answer depends only on these two.
• 單次掃描 / One pass：只從頭到尾走過陣列一次就得到答案，效率高。 / Walking through the array from start to end exactly once to compute the answer.
• 時間複雜度 / Time complexity：用來描述演算法隨輸入變大時「大約要做多少步」的記號，例如 O(n)。 / Notation describing roughly how many steps an algorithm takes as the input grows, e.g. O(n).

思路

這題要讓 (nums[i]-1)*(nums[j]-1) 最大。因為題目保證所有數字都 >= 1，所以每個 nums[k]-1 都是 >= 0 的非負數，兩個非負數相乘不會有「負負得正」的意外。既然乘積由兩個因子決定，而且兩個因子都非負且會隨原數字變大而變大，那麼要讓乘積最大，最直覺的想法就是：挑陣列裡最大的兩個數字，減 1 後相乘。最直接的暴力法是用兩層迴圈枚舉所有的 (i, j) 配對，逐一計算乘積並取最大值，這樣是 O(n²)。在 n 只有 500 的情況下其實完全跑得動，但我們可以做得更漂亮。既然答案只跟「最大」和「次大」兩個值有關，我們只需要一次掃描，邊走邊維護目前看到的最大值 max1 與次大值 max2：每遇到一個新數字，如果它比 max1 大，就把舊的 max1 降級成 max2，再讓新數字當 max1；否則若它比 max2 大，就更新 max2。掃描結束後答案就是 (max1-1)*(max2-1)。這裡的關鍵不變量是：在任何時刻，max1 與 max2 永遠是「到目前為止」最大的兩個數。

We want to maximize (nums[i]-1)*(nums[j]-1). Since every nums[k] >= 1, each factor nums[k]-1 is non-negative, so there are no sign surprises — a bigger original number always gives a bigger (or equal) factor. The product is largest when both factors are largest, which means we simply want the two biggest numbers in the array, each minus one. The most obvious brute-force approach is two nested loops over all (i, j) pairs, computing every product and keeping the max — that is O(n²). With n at most 500 this is perfectly fine, but we can do better. Because the answer depends only on the largest and second-largest values, a single pass suffices: as we scan, we keep max1 (largest so far) and max2 (second-largest so far). For each new number, if it beats max1, the old max1 is demoted to max2 and the new number becomes max1; otherwise if it only beats max2, we update max2. The invariant is that at every moment max1 and max2 hold the two biggest values seen so far, so at the end (max1-1)*(max2-1) is the answer.

逐步走查 / Walkthrough

以 nums = [3,4,5,2] 為例，初始 max1 = 0, max2 = 0（因為所有數字 >= 1，用 0 當起始安全）。 Using nums = [3,4,5,2], start with max1 = 0, max2 = 0 (safe because every number is >= 1).

掃描結束 / End of scan：(max1-1)*(max2-1) = (5-1)*(4-1) = 4*3 = 12。✅

Solution — C

/*
 * 演算法 / Algorithm:
 * 只跟「最大值 max1」與「次大值 max2」有關，所以單次掃描維護這兩個值即可。
 * We only need the two largest values, so one pass tracking max1 and max2 suffices.
 * 最後回傳 (max1-1)*(max2-1)。 / Finally return (max1-1)*(max2-1).
 */

int maxProduct(int* nums, int numsSize) {
    // max1 是目前最大值，max2 是次大值；起始 0 安全，因為所有 nums[i] >= 1
    // max1 = largest so far, max2 = second largest; 0 is a safe start since all nums[i] >= 1
    int max1 = 0;
    int max2 = 0;

    // 從頭到尾走過陣列一次 / walk through the array exactly once
    for (int i = 0; i < numsSize; i++) {
        int num = nums[i];  // 取出目前這個數字 / read the current element

        if (num > max1) {
            // 新數字比最大值還大：舊的 max1 降級為 max2，新數字成為 max1
            // new number beats the max: old max1 becomes max2, new number becomes max1
            max2 = max1;
            max1 = num;
        } else if (num > max2) {
            // 新數字比不過 max1，但比 max2 大：只更新 max2
            // beats only the second largest: update max2 only
            max2 = num;
        }
        // 否則 num 太小，兩個都不更新 / otherwise num is too small, no update
    }

    // 兩個最大值各減 1 後相乘就是答案 / multiply the two largest (each minus 1)
    return (max1 - 1) * (max2 - 1);
}

Solution — C++

/*
 * 演算法 / Algorithm:
 * 單次掃描維護最大值與次大值，最後回傳 (max1-1)*(max2-1)。
 * One pass tracking the largest and second-largest, then return (max1-1)*(max2-1).
 */

class Solution {
public:
    int maxProduct(vector<int>& nums) {
        // max1 目前最大值，max2 次大值；用 0 起始安全（所有元素 >= 1）
        // max1 = largest, max2 = second largest; start at 0 (all elements >= 1)
        int max1 = 0;
        int max2 = 0;

        // range-for：直接依序取出 vector 中每個元素，不必手動管理索引
        // range-for loop: iterate each element of the vector without manual indexing
        for (int num : nums) {
            if (num > max1) {
                // 舊 max1 降為 max2，新數字成為 max1
                // old max1 demoted to max2, new number becomes max1
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                // 只比 max2 大，更新次大值 / beats only max2, update it
                max2 = num;
            }
        }

        // 回傳兩個最大值各減 1 的乘積 / return product of the two largest, each minus 1
        return (max1 - 1) * (max2 - 1);
    }
};

複雜度 / Complexity

• Time: O(n) — 我們只把陣列從頭到尾掃描一次，每個元素做常數次比較，n 是陣列長度。相較暴力法的 O(n²) 更快。 / We scan the array once, doing a constant amount of work per element; n is the array length — faster than the brute-force O(n²).
• Space: O(1) — 只用了 max1、max2 兩個額外變數，與輸入大小無關。 / Only two extra variables max1, max2, independent of input size.

Pitfalls & Edge Cases

• 不是回傳最大乘積本身，而是「減 1 後」的乘積 / Return the product of values minus one, not the raw product：容易忘記那個 -1，導致答案偏大。程式碼在最後才統一減 1。 / Forgetting the -1 gives a too-large answer; the code applies it only at the return step.
• 兩個索引必須不同 / The two indices must differ：我們取的是最大值與次大值兩個不同位置，不會拿同一個元素乘自己。 / We take the largest and the second largest at different positions, never squaring a single element.
• 重複的最大值是合法的 / Duplicate maximums are fine：像 [5,5] 這種，max1=5, max2=5，答案 (5-1)*(5-1)=16 正確——它們是不同索引的相同數值。 / For [5,5], both become 5 at different indices, giving 16 correctly.
• 起始值用 0 而非負數或 INT_MIN / Initialize to 0, not a negative sentinel：因為題目保證 nums[i] >= 1，任何真實元素都會 > 0，能正確蓋掉初始的 0；若資料可能含 0 或負數就需改用更小的哨兵值。 / Since nums[i] >= 1, real elements always exceed the initial 0; if inputs could be 0 or negative you would need a smaller sentinel.
• 不會溢位 / No overflow：最大值約為 (1000-1)*(1000-1) ≈ 998001，遠在 32 位元 int 範圍內。 / The max is about 999*999 ≈ 998001, well within 32-bit int.