Сайт: https://easyoffer.ru/
Все каналы: t.me/+xGeAw6ckJ4liYzQy
Контакт для рекламы: @sendme_ads
Post #1053
119
Задача: 363. Max Sum of Rectangle No Larger Than K
Сложность: hard
Дана матрица размером m x n и целое число k, вернуть максимальную сумму прямоугольника в матрице, такая что его сумма не превышает k.
Гарантируется, что будет прямоугольник с суммой, не превышающей k.
Пример:
👨💻 Алгоритм:
1⃣Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k.
2⃣Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult.
3⃣Вернуть максимальную найденную сумму.
😎 Решение:
Ставь 👍 и забирай 📚 Базу знаний
Сложность: 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
}
}Ставь 👍 и забирай 📚 Базу знаний
