Задача: 363. Max Sum of Rectangle No Larger Than K
Сложность: hard

Дана матрица размером 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 {
    private $result;

    function __construct() {
        $this->result = PHP_INT_MIN;
    }

    private function updateResult($nums, $k) {
        $sum = 0;
        $sortedSum = [0];

        foreach ($nums as $num) {
            $sum += $num;
            $idx = $this->binarySearch($sortedSum, $sum - $k);
            if ($idx < count($sortedSum)) {
                $this->result = max($this->result, $sum - $sortedSum[$idx]);
            }
            array_push($sortedSum, $sum);
            sort($sortedSum);
        }
    }

    private function binarySearch($arr, $target) {
        $left = 0;
        $right = count($arr);
        while ($left < $right) {
            $mid = intval(($left + $right) / 2);
            if ($arr[$mid] < $target) $left = $mid + 1;
            else $right = $mid;
        }
        return $left;
    }

    function maxSumSubmatrix($matrix, $k) {
        $rows = count($matrix);
        $cols = count($matrix[0]);

        for ($i = 0; $i < $rows; $i++) {
            $rowSum = array_fill(0, $cols, 0);
            for ($row = $i; $row < $rows; $row++) {
                for ($col = 0; $col < $cols; $col++) {
                    $rowSum[$col] += $matrix[$row][$col];
                }
                $this->updateResult($rowSum, $k);
                if ($this->result == $k) {
                    return $this->result;
                }
            }
        }
        return $this->result;
    }
}

Ставь 👍 и забирай 📚 Базу знаний