moea_joint_essay
109年
[資訊] 資訊管理、程式設計
第 二 題
📖 題組：
給定一陣列名稱為 NUM，包含 n 個不重複整數(n > 2)，請撰寫虛擬程式碼找出該陣列中元素兩兩乘積最大者(即 Maximum pairwise product，變數名稱為 maxprod，maxprod = maximum (NUM[i] * NUM[j], i <> j) )，完成下列 2 項子題。（共 2 題，共 25 分）
給定一陣列名稱為 NUM，包含 n 個不重複整數(n > 2)，請撰寫虛擬程式碼找出該陣列中元素兩兩乘積最大者(即 Maximum pairwise product，變數名稱為 maxprod，maxprod = maximum (NUM[i] * NUM[j], i <> j) )，完成下列 2 項子題。（共 2 題，共 25 分）
📝 此題為申論題，共 2 小題
小題 (二)
請在演算法時間複雜度須為 O(n)的限制下，撰寫虛擬程式碼。(請注意，如作答內容之演算法時間複雜度經分析為 O(n²)，本子題僅給 5 分)（15 分）
思路引導 VIP
利用 O(n) 一次遍歷，更新 max1, max2, min1, min2，最後輸出乘積較大者。
小題 (一)
請說明欲撰寫之虛擬程式碼的主要程式邏輯。（10 分）
思路引導 VIP
找出陣列中兩元素相乘最大值的邏輯：這兩個數可能是陣列中最大的兩個正數相乘，也可能是最小的兩個負數相乘(負負得正)。因此只需在一次掃描中記錄下最大及次大值，以及最小及次小值即可，兩者乘積取大者即為答案。