363. Max Sum of Rectangle No Larger Than K
leetcode hard
#array#csharp#hard#hash-table#leetcode#math#matrix#sort
Task
Дана матрица размером 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).
C# solution
matched/originalusing System;
using System.Collections.Generic;
public class Solution {
private int result = int.MinValue;
private void UpdateResult(int[] nums, int k) {
int sum = 0;
var sortedSum = new SortedSet<int> { 0 };
foreach (int num in nums) {
sum += num;
var x = sortedSum.GetViewBetween(sum - k, int.MaxValue);
if (x.Count > 0) {
result = Math.Max(result, sum - x.Min);
}
sortedSum.Add(sum);
}
}
public int MaxSumSubmatrix(int[][] matrix, int k) {
int rows = matrix.Length;
int cols = matrix[0].Length;
for (int i = 0; i < rows; i++) {
var rowSum = new int[cols];
for (int row = i; row < rows; row++) {
for (int col = 0; col < cols; col++) {
rowSum[col] += matrix[row][col];
}
UpdateResult(rowSum, k);
if (result == k) {
return result;
}
}
}
return result;
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
private int result = int.MinValue;
private void UpdateResult(vector<int>& nums, int k) {
int sum = 0;
var sortedSum = new SortedSet<int> { 0 };
foreach (int num in nums) {
sum += num;
var x = sortedSum.GetViewBetween(sum - k, int.MaxValue);
if (x.size() > 0) {
result = max(result, sum - x.Min);
}
sortedSum.push_back(sum);
}
}
public int MaxSumSubmatrix(int[][] matrix, int k) {
int rows = matrix.size();
int cols = matrix[0].size();
for (int i = 0; i < rows; i++) {
var rowSum = new int[cols];
for (int row = i; row < rows; row++) {
for (int col = 0; col < cols; col++) {
rowSum[col] += matrix[row][col];
}
UpdateResult(rowSum, k);
if (result == k) {
return result;
}
}
}
return result;
}
}Java solution
matched/originalclass Solution {
int result = Integer.MIN_VALUE;
void updateResult(int[] nums, int k) {
int sum = 0;
TreeSet<Integer> sortedSum = new TreeSet<>();
sortedSum.add(0);
for (int num : nums) {
sum += num;
Integer x = sortedSum.ceiling(sum - k);
if (x != null)
result = Math.max(result, sum - x);
sortedSum.add(sum);
}
}
public int maxSumSubmatrix(int[][] matrix, int k) {
int[] rowSum = new int[matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
Arrays.fill(rowSum, 0);
for (int row = i; row < matrix.length; row++) {
for (int col = 0; col < matrix[0].length; col++)
rowSum[col] += matrix[row][col];
updateResult(rowSum, k);
if (result == k)
return result;
}
}
return result;
}
}JavaScript solution
matched/originalclass 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;
}
}Python solution
matched/originalclass Solution:
def __init__(self):
self.result = float('-inf')
def updateResult(self, nums, k):
import bisect
sum_, prefix_sums = 0, [0]
for num in nums:
sum_ += num
idx = bisect.bisect_left(prefix_sums, sum_ - k)
if idx < len(prefix_sums):
self.result = max(self.result, sum_ - prefix_sums[idx])
bisect.insort(prefix_sums, sum_)
def maxSumSubmatrix(self, matrix, k):
rows, cols = len(matrix), len(matrix[0])
for i in range(rows):
row_sum = [0] * cols
for row in range(i, rows):
for col in range(cols):
row_sum[col] += matrix[row][col]
self.updateResult(row_sum, k)
if self.result == k:
return self.result
return self.resultGo solution
matched/originalpackage main
import (
"math"
"sort"
)
type Solution struct {
result int
}
func Constructor() Solution {
return Solution{result: math.MinInt32}
}
func (this *Solution) updateResult(nums []int, k int) {
sum := 0
sortedSum := []int{0}
for _, num := range nums {
sum += num
idx := sort.Search(len(sortedSum), func(i int) bool { return sortedSum[i] >= sum-k })
if idx < len(sortedSum) {
this.result = int(math.Max(float64(this.result), float64(sum-sortedSum[idx])))
}
sortedSum = append(sortedSum, sum)
sort.Ints(sortedSum)
}
}
func (this *Solution) maxSumSubmatrix(matrix [][]int, k int) int {
rows := len(matrix)
cols := len(matrix[0])
for i := 0; i < rows; i++ {
rowSum := make([]int, cols)
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
}Explanation
Algorithm
Создать вспомогательную функцию updateResult, которая будет находить максимальную сумму подмассива в одномерном массиве, не превышающую k.
Преобразовать каждую подматрицу в одномерный массив и применить к ней функцию updateResult.
Вернуть максимальную найденную сумму.
😎