# Untitled

unknown
plain_text
a month ago
1.9 kB
4
Indexable
Never
```def find_maximum_sum_of_beauties(grid, N):
def compute_beauty(max_val, min_val):
return max_val - min_val

# Precompute min and max values for each sub-grid
min_dp = [[[0] * N for _ in range(N)] for _ in range(N)]
max_dp = [[[0] * N for _ in range(N)] for _ in range(N)]

for size in range(N):
for i in range(N - size):
for j in range(N - size):
min_val = float('inf')
max_val = float('-inf')
for x in range(i, i + size + 1):
for y in range(j, j + size + 1):
min_val = min(min_val, grid[x][y])
max_val = max(max_val, grid[x][y])
min_dp[i][j][size] = min_val
max_dp[i][j][size] = max_val

max_sum_beauty = 0

# Iterate over all possible sub-grids
for size1 in range(N):
for i1 in range(N - size1):
for j1 in range(N - size1):
beauty1 = compute_beauty(max_dp[i1][j1][size1], min_dp[i1][j1][size1])

for size2 in range(N):
for i2 in range(N - size2):
for j2 in range(N - size2):
if (i1 <= i2 < i1 + size1 + 1 or i2 <= i1 < i2 + size2 + 1) or \
(j1 <= j2 < j1 + size1 + 1 or j2 <= j1 < j2 + size2 + 1):
continue

beauty2 = compute_beauty(max_dp[i2][j2][size2], min_dp[i2][j2][size2])

max_sum_beauty = max(max_sum_beauty, beauty1 + beauty2)

return max_sum_beauty