Vấn đề
Cần viết hàm JS nhận mảng số không âm arr và số num (num < arr.length). Chia mảng thành num mảng con liên tiếp không rỗng sao cho tổng lớn nhất trong các mảng con là nhỏ nhất có thể. Trả về tổng lớn nhất đó.
Ví dụ:
const arr = [5, 1, 4, 8, 7]; const num = 2;
Kết quả:
const output = 15;
Giải thích:
Chia thành [5,1,4] và [8,7] -> tổng lần lượt 10 và 15 -> max = 15 (tối thiểu).
Ví dụ
Mã thực hiện:
const arr = [5, 1, 4, 8, 7]; const num = 2; const splitArray = (arr = [], num = 1) => { let max = 0; let sum = 0; const split = (arr, mid) => { let part = 1; let tempSum = 0; for (let num of arr) { if (tempSum + num > mid) { tempSum = num; part++; } else { tempSum += num; } } return part; }; for (let num of arr) { max = Math.max(max, num); sum += num; }; let low = max; let high = sum; while (low < high) { let mid = Math.floor((high+low)/2); let part = split(arr, mid); if (part > num) { low = mid + 1; } else { high = mid; } } return low; }; console.log(splitArray(arr, num));
Giải thích code:
Dùng tìm kiếm nhị phân trên khoảng [max(arr), sum(arr)] để tìm giá trị nhỏ nhất cho phép chia thành ≤ num phần.
Kết quả
Kết quả in ra console:
15