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

ปัญหา

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

ฟังก์ชันของเราควรแบ่งอาร์เรย์ arr ออกเป็น num กลุ่มที่อยู่ติดกัน (ไม่ว่าง) ในลักษณะที่เราไม่ทิ้งองค์ประกอบไว้

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

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

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

ป้อนข้อมูล

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));

ผลลัพธ์

23