ผลรวมค่าเฉลี่ยของพาร์ติชันที่มากที่สุดใน JavaScript

ปัญหา

เราต้องเขียนฟังก์ชัน JavaScript ที่รับอาร์เรย์ของตัวเลข arr เป็นอาร์กิวเมนต์แรก และตัวเลข num (num <= ขนาดของ arr) เป็นอาร์กิวเมนต์ที่สอง

ฟังก์ชันควรแบ่งพาร์ติชันอาร์เรย์ arr เป็นสูงสุด num กลุ่มที่ติดกัน (non-empty) โดยไม่ทิ้งองค์ประกอบใดๆ

จากพาร์ติชันทั้งหมดที่เป็นไปได้ ฟังก์ชันควรเลือกพาร์ติชันที่ผลรวมของค่าเฉลี่ยของทุกกลุ่มมีค่ามากที่สุด

และสุดท้ายเราควรคืนค่าผลรวมมากที่สุดนี้

ตัวอย่างเช่น หากอินพุตคือ

อินพุต

const arr = [10, 2, 3, 4, 10];
const num = 3;

เอาต์พุต

const output = 23;

คำอธิบายเอาต์พุต

เพราะหากเราแบ่งพาร์ติชันอาร์เรย์แบบนี้

[10], [2, 3, 4], [10]

ผลรวมของค่าเฉลี่ยจะเป็น

10 + (9)/3 + 10 = 23

ซึ่งเป็นค่ามากที่สุดในทุกพาร์ติชัน

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

const arr = [10, 2, 3, 4, 10];
const num = 3;
const greatestSum = (arr, num) => {
  const sum = (arr = []) => arr.reduce((acc, num) => acc + num, 0);
  let matrix = new Array(num + 1).fill(0).map(() => new Array(arr.length + 1).fill(0));
  for (let index = arr.length; index >= 0; index--) {
    const current = new Array(num + 1).fill(0).map(() => new Array(arr.length + 1).fill(0));
    for (let currentK = num; currentK >= 0; currentK--) {
      for (let count = arr.length - 1; count >= 0; count--) {
        if (index === arr.length && currentK === num) {
          current[currentK][count] = 0;
        } else if (index < arr.length && currentK < num) {
          current[currentK][count] = Math.max(
            matrix[currentK][count + 1],
            matrix[currentK + 1][0] + sum(arr.slice(index - count, index + 1)) / (count + 1)
          );
        } else {
          current[currentK][count] = -Infinity;
        }
      }
    }
    matrix = current;
  }
  return matrix[0][0];
};
console.log(greatestSum(arr, num));

ผลรวมค่าเฉลี่ยของพาร์ติชันที่มากที่สุดใน JavaScript

ปัญหา

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

ผลลัพธ์