Tổng lớn nhất của trung bình các phân vùng trong JavaScript

Vấn đề

Chúng ta cần viết một hàm JavaScript nhận vào một mảng số arr làm đối số thứ nhất, và một số num (num <= arr.length) làm đối số thứ hai. Hàm phải phân vùng mảng arr thành tối đa num nhóm liền kề (không rỗng) sao cho không bỏ sót phần tử nào. Từ tất cả các phân vùng đó, hàm phải chọn phân vùng mà tổng trung bình của tất cả các nhóm là lớn nhất. Trả về tổng lớn nhất này.

Ví dụ, nếu đầu vào là:

Đầu vào

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

Đầu ra

const output = 23;

Giải thích

Vì nếu phân vùng mảng như sau: [10], [2, 3, 4], [10]. Tổng trung bình: 10 + 9/3 + 10 = 23. Đây là lớn nhất trong tất cả phân vùng.

Ví dụ

Dưới đây là mã thực hiện:

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

Kết quả

23