# 363. Max Sum of Rectangle No Larger Than K

## Problem

Given a 2-d array, with integer values (positive and negative). Given an integer k. Find the maximum sub-matrix sum <= k.

## Solution

We can use dynamic programming to calculate the sums of the sub-matrices. Then by enumerating all the sub-matrices, we can get the answer. Complexity O(n^2m^2). An improve would be only enumerate the top, bottom and right border of the sub-matrix. Since we want For the left border we just select the left that maximize sum[right] - sum[left] subject to <= k, where sum is the sum of the sub-matrix with left=0 to right=index and the current top and bottom border. To maximize it, we can use binary search tree. It is equivalent to maximizing sum[left] subject to >= sum[right] - k. We insert the sum values into the tree, every time we query it the lower_bound of sum[right] - k, as we iterate all the right. The complexity is O(n^2mlogm).

Note: Python doesn't have a built-in binary search tree. We need to write our own.

## Code

class Node:
def __init__(self, value):
self.left = None
self.right = None
self.val = value

class BinarySearchTree:
def __init__(self):
self.root = None

def lower_bound(self, value):
node = self.root
ret = None
while node is not None:
if value < node.val:
ret = node.val
node = node.left
elif value == node.val:
ret = node.val
return ret
else:
node = node.right
return ret

def insert(self, value):
if self.root is None:
self.root = Node(value)
return
last_node = None
node = self.root
while node is not None:
last_node = node
if value < node.val:
node = node.left
else:
node = node.right
if value < last_node.val:
last_node.left = Node(value)
else:
last_node.right = Node(value)

class Solution:
def maxSumSubmatrix(self, matrix: List[List[int]], k: int) -> int:
if len(matrix) > len(matrix[0]):
new_matrix = []
for i in range(len(matrix[0])):
new_matrix.append([])
for j in range(len(matrix)):
new_matrix[i].append(matrix[j][i])
matrix = new_matrix
num_rows = len(matrix)
num_cols = len(matrix[0])
sum_matrix = [[0 for j in range(num_cols + 1)] for i in range(num_rows + 1)]
for i in range(num_rows):
for j in range(num_cols):
sum_matrix[i + 1][j + 1] = matrix[i][j] + sum_matrix[i + 1][j] + sum_matrix[i][j + 1] - sum_matrix[i][j]

ret = - int(1 << 30)
for height in range(1, num_rows + 1):
for top in range(1, num_rows - height + 1 + 1):
bottom = top + height - 1
bst = BinarySearchTree()
bst.insert(0)
for right in range(1, num_cols + 1):
current_sum = sum_matrix[bottom][right] - sum_matrix[top - 1][right]
left_sum = bst.lower_bound(current_sum - k)
# print(right, current_sum, left_sum)
if left_sum is not None:
ret = max(ret, current_sum - left_sum)
bst.insert(current_sum)
return ret