การแยกตัวเลขเพื่อให้ผลคูณสูงสุดใน JavaScript

ปัญหา

แยก integer n เป็นผลรวมของอย่างน้อย 2 จำนวนเต็มบวก ให้ผลคูณสูงสุด

ตัวอย่าง

n = 10 -> 3+3+4 = 10, product = 36

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

const num = 10;

const breakInt = (num = 2) => {
  const dp = new Array(num + 1).fill(0);
  dp[0] = 0;
  dp[1] = 1;
  for (let i = 2; i <= num; i++) {
    for (let j = 1; 2 * j <= i; j++) {
      dp[i] = Math.max(dp[i], Math.max(j, dp[j]) * Math.max(i - j, dp[i - j]));
    }
  }
  return dp[num];
};

console.log(breakInt(num));

ผลลัพธ์

36

คำอธิบาย

DP: dp[i] = max product สำหรับ i

ลองแบ่ง i = j + (i-j) ใช้ max(j, dp[j]) * max(i-j, dp[i-j]) (เลือกแยกหรือไม่แยก)

Mathematical insight: แยกเป็น 3 ให้มากที่สุด (3*3 > 2*2*2, 3*1 < 2*2) -> O(1) solution

const integerBreak = (n) => {
  if (n <= 3) return n - 1;
  const q = Math.floor(n / 3), r = n % 3;
  if (r === 0) return 3 ** q;
  if (r === 1) return 3 ** (q - 1) * 4;
  return 3 ** q * 2;
};