ผลรวมผลคูณสูงสุดของสองอาร์เรย์ (Maximum Sum of Products) - JavaScript

หาผลรวมผลคูณสูงสุด (Maximum Sum of Products) โดยจับคู่เอลีเมนต์ของสองอาร์เรย์ที่มีขนาดเท่ากัน

หลักการ (Rearrangement Inequality)

ผลรวมสูงสุดได้เมื่อจับคู่ ค่ามากกับค่ามาก, ค่าน้อยกับค่าน้อย (เรียงทั้งคู่แบบเดียวกัน)

ตัวอย่างโค้ด

const arr1 = [5, 1, 3, 4, 2];
const arr2 = [8, 10, 9, 7, 6];

const greatestProduct = (a1, a2) => {
  if (a1.length !== a2.length) return false;
  
  const sorted1 = [...a1].sort((a, b) => b - a); // Descending
  const sorted2 = [...a2].sort((a, b) => b - a); // Descending
  
  return sorted1.reduce((sum, val, i) => sum + val * sorted2[i], 0);
};

console.log(greatestProduct(arr1, arr2));

ผลลัพธ์

130

การคำนวณ

Sorted: [5,4,3,2,1] × [10,9,8,7,6]
= 5×10 + 4×9 + 3×8 + 2×7 + 1×6
= 50 + 36 + 24 + 14 + 6 = 130

ทฤษฎี

Rearrangement Inequality: สำหรับลำดับที่เรียงเดียวกัน ผลรวมผลคูณจะสูงสุด สำหรับลำดับตรงข้าม จะต่ำสุด