Задача: 363. Max Sum of Rectangle No Larger Than K
Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k.
Гарантируется, что будет прямоугольник с суммой, не превышающей k.
Пример:
Input: matrix = [[1,0,1],[0,-2,3]], k = 2
Output: 2
Explanation: Because the sum of the blue rectangle [[0, 1], [-2, 3]] is 2, and 2 is the max number no larger than k (k = 2).
👨💻 Алгоритм:
1⃣Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k.
2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult.
3⃣Вернуть максимальную найденную сумму.
😎 Решение:
class Solution {
constructor() {
this.result = Number.NEGATIVE_INFINITY;
}
updateResult(nums, k) {
let sum = 0;
const sortedSum = [0];
for (let num of nums) {
sum += num;
let idx = this.binarySearch(sortedSum, sum - k);
if (idx < sortedSum.length) {
this.result = Math.max(this.result, sum - sortedSum[idx]);
}
sortedSum.push(sum);
sortedSum.sort((a, b) => a - b);
}
}
binarySearch(arr, target) {
let left = 0, right = arr.length;
while (left < right) {
let mid = Math.floor((left + right) / 2);
if (arr[mid] < target) left = mid + 1;
else right = mid;
}
return left;
}
maxSumSubmatrix(matrix, k) {
const rows = matrix.length;
const cols = matrix[0].length;
for (let i = 0; i < rows; i++) {
let rowSum = Array(cols).fill(0);
for (let row = i; row < rows; row++) {
for (let col = 0; col < cols; col++) {
rowSum[col] += matrix[row][col];
}
this.updateResult(rowSum, k);
if (this.result === k) {
return this.result;
}
}
}
return this.result;
}
}👉Новости 👉База вопросов
