題組內容

六、給定一陣列名稱為 NUM，包含 n 個不重複整數(n ＞ 2)，請撰寫虛擬程式碼找出該陣 列 中 元 素 兩 兩 乘 積 最 大 者(即 Maximum pairwise product， 變 數名 稱 為 maxprod， maxprod = maximum (NUM[i] * NUM[j], i ＜＞ j) )，完成下列 2 項子題。

(二)請在演算法時間複雜度須為 O(n)的限制下，撰寫虛擬程式碼。(請注意，如作答內容之 演算法時間複雜度經分析為 O(n2)，本子題僅給 5 分)（15 分）

詳解 (共 1 筆)

詳解 提供者：hchungw

說明

  1. 初始化：
    • 初始化 max1 和 max2 為負無窮大（-infinity），表示當前找到的兩個最大的數。
  2. 遍歷陣列：
    • 使用一個迴圈遍歷整個陣列 NUM。
    • 如果當前元素大於 max1，則將 max1 的值賦給 max2，並將當前元素的值賦給 max1。這樣確保 max1 和 max2 始終是陣列中最大的兩個數。
    • 如果當前元素不大於 max1 但大於 max2，則將當前元素的值賦給 max2。
  3. 計算乘積：
    • 遍歷結束後，max1 和 max2 將會是陣列中最大的兩個數，計算這兩個數的乘積即為 maxprod。

時間複雜度分析

該演算法只需遍歷陣列一次，因此時間複雜度為 O(n)，其中 n 是陣列的長度。這滿足了題目中要求的 O(n) 時間複雜度限制。