Задача: 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 {
    var result = Int.min

    func updateResult(_ nums: [Int], _ k: Int) {
        var sum = 0
        var sortedSum = Set<Int>()
        sortedSum.insert(0)

        for num in nums {
            sum += num
            if let x = sortedSum.first(where: { $0 >= sum - k }) {
                result = max(result, sum - x)
            }
            sortedSum.insert(sum)
        }
    }

    func maxSumSubmatrix(_ matrix: [[Int]], _ k: Int) -> Int {
        let rows = matrix.count
        let cols = matrix[0].count
        var rowSum = [Int](repeating: 0, count: cols)

        for i in 0..<rows {
            rowSum = [Int](repeating: 0, count: cols)
            for row in i..<rows {
                for col in 0..<cols {
                    rowSum[col] += matrix[row][col]
                }
                updateResult(rowSum, k)
                if result == k {
                    return result
                }
            }
        }
        return result
    }
}

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