求完整代码有一个 n*n 大小的蛋糕,因为烤蛋糕的烤箱火力不均匀,每个位置上的美味值都不一样,有些地方烤糊了,所以有些位置上的美味值出现了负值。现在只能从这个蛋糕上切下一块矩形的区域,并且要保证所切下的区域美味值最大
时间: 2023-06-05 15:07:50 浏览: 49
对于这个问题,可以使用二维前缀和来解决。首先,计算出每个位置上的美味值的前缀和,然后对于每个切割区域,使用前缀和快速计算出该区域的美味值之和。最后,枚举所有可能的切割区域,通过比较其美味值之和来确定最大值即可。代码如下:
```python
def max_sum_submatrix(matrix):
m, n = len(matrix), len(matrix[0])
pre_sum = [[0] * (n+1) for _ in range(m+1)]
# 计算前缀和
for i in range(1, m+1):
for j in range(1, n+1):
pre_sum[i][j] = pre_sum[i-1][j] + pre_sum[i][j-1] - pre_sum[i-1][j-1] + matrix[i-1][j-1]
# 枚举所有可能的切割区域
max_sum = float('-inf')
for i1 in range(1, m+1):
for j1 in range(1, n+1):
for i2 in range(i1, m+1):
for j2 in range(j1, n+1):
sub_sum = pre_sum[i2][j2] - pre_sum[i1-1][j2] - pre_sum[i2][j1-1] + pre_sum[i1-1][j1-1]
max_sum = max(max_sum, sub_sum)
return max_sum
```
注意:这里的复杂度是 $O(n^4)$,如果 $n$ 很大会超时。可以使用 Kadane 算法改进到 $O(n^3)$ 或分治法改进到 $O(n^2 \log{n})$。