orz
《最大子矩阵》
给定一个正整数、负整数和 0 组成的 N × M 矩阵，编写代码找出元素总和最大的子矩阵。
返回一个数组 [r1, c1, r2, c2]，其中 r1, c1 分别代表子矩阵左上角的行号和列号，r2, c2 分别代表右下角的行号和列号。若有多个满足条件的子矩阵，返回任意一个均可。
示例：
输入：
[
[-1,0],
[0,-1]
]
输出：[0,1,0,1]
1 <= matrix.length, matrix[0].length <= 200
拿到题先开始分析，属于二维区间DP，这个题显然是LMS的升级版
$dp(i,j)$可能由$dp(i-1,j)$和$dp(i,j-1)$状态转移而来
并且存在状态转移中断的可能
所以我们定义$dp(i,j)$表示以$matrix(i,j)$元素为矩阵右下角（即该元素必选）的最大子矩阵
第一次，完全错了：
初步设想状态转移方式为
①右扩$dp(i-1,j)\to dp(i,j)$：如果右扩，则新增的并不是$matrix(i,j)$，而是$\sum matrix(0…i,j)$，若$\sum matrix(0…i,j)>0$则转移，否则不转移；
②下扩$dp(i,j-1)\to dp(i,j)$：如果下扩，则新增是$\sum matrix(i,0…j)$，若$\sum matrix(i,0…j)>0$则转移，否则不转移。
显然发现这个转移方式有问题：
第二次，然而还是有错：
问题一：没有考虑状态中断。在状态转移中断之后，不是从0开始计算的，而是从上一次中断开始加和，所以需要第三维来记录上一个起点。并且根据题意要求输出坐标，所以也正好需要专门记录。
问题二：和LMS一样容易犯的老错误，状态$dp(i,j)$中$matrix(i,j)$是必选的！不是根据新增元素，以右扩为例，即不是根据$\sum matrix(0…i,j)$大小来判断是否转移，而是应该判断$dp(i-1,j)>0$才能转移，因为根据必须以$matrix(i,j)$为结尾的$dp(i,j)$定义，只要$dp(i-1,j)>0$，那么加上新增元素无论大还是小都比中断状态转移更大。
所以综合下来，状态转移方程为：
①右扩$dp(i-1,j)\to dp(i,j)$：如果右扩，若$dp(i-1,j)>0$则转移：
否则不转移：
②下扩$dp(i,j-1)\to dp(i,j)$：如果下扩，若$dp(i,j-1)>0$则转移：
否则不转移：
代码：
def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
#dp[i][j]：以nums[i][j]为最右下角的矩阵的最小值
n = len(matrix) #行
m = len(matrix[0]) #列
dp = [[(0,0,0)]*m for i in range(n)] #(nums,i,j) 分别代表该位值、上一个中断处
#start
for i in range(n):
for j in range(m):
#右拓：dp(i,j)可能由dp(i,j-1)转移
right_rec = float('-inf')
if j>0: #边界判断
row_sums = 0
#【关键点】中断之后，不是从0开始计算的，而是从上一次中断开始加和，所以需要第三维来记录上一个起点。同时根据题意，也需要专门记录。
for row_index in range(dp[i][j-1][1],i+1):
row_sums += matrix[row_index][j]
#若和增大，则可以转移，否则不转移（初始值）
# if row_sums>=0: #【错误点】：和LIS问题一样，状态转移公式出错,dp[i][j]中matrix[i][j]是必选的！转不转移是由源状态是否>=0来判断！
if dp[i][j-1][0]>=0:
right_rec = dp[i][j-1][0] + row_sums
#下拓：dp(i,j)可能由dp(i-1,j)转移
down_rec = float('-inf')
if i>0:
col_sums = 0
for col_index in range(dp[i-1][j][2],j+1):
col_sums += matrix[i][col_index]
if dp[i-1][j][0]>=0:
down_rec = dp[i-1][j][0] + col_sums
#判断从哪个状态转移或未转移
if right_rec==float('-inf') and down_rec==float('-inf'): #错误点，inf少打了个负号...TMD找了半天BUG
dp[i][j] = (matrix[i][j],i,j) #未发生转移，转移中断，设置为初始值，即matrix[i][j]
else:
#转移成功，这里要记录，本次矩阵起点与上一个转移状态起点一致
if right_rec>down_rec:
dp[i][j] = (right_rec,dp[i][j-1][1],dp[i][j-1][2])
else:
dp[i][j] = (down_rec,dp[i-1][j][1],dp[i-1][j][2])
#在dp矩阵中找值最大的状态
max_rec = float('-inf')
startxy = (0,0)
endxy = (0,0)
for i in range(n):
for j in range(m):
if dp[i][j][0]>max_rec:
max_rec = dp[i][j][0]
startxy = (dp[i][j][1],dp[i][j][2])
endxy = (i,j)
return [startxy[0],startxy[1],endxy[0],endxy[1]]然而还是有问题…
举个例子：
-1 -2 -9 6
8 -9 -3 -6
2 9 -7 -6在这个输入中，主要关注左下角四个，其dp矩阵为
8 -1
10 10这里显然错了！
按照上面的算法，dp(2,1)只能来源于dp(2,0)或dp(1,1)。dp(1,1)<0直接跳过，dp(2,0)所得矩阵的起点是(2,0)，也就是说是由这两个数组成的矩阵：
8
2那么在右扩的时候，计算起点只能是这个4个数的方格如下，成为了10+(-9)+9=10：
8 -9
2 9而正确答案是2+9=11：
2 9上面的算法没给出这种可能性。所以思路是完全错误了，通过率为50%（悲）。
虽然有错，但是思路是很重要的。
正确答案
正确思路是对矩阵进行降维，将二维问题拆解为一维LMS问题。
实际上是一个巧解…..
对于一个$n×m$的矩阵，有$1+2+\cdots+n$种横向选择方案，我们堆每一种横向选择方案进行列求和，存储进一个$sum[]$数组中，也就是将所有行选法$n×m$降维成了$1×m$，变成了一个一维序列。
然后我们再对每个$sum[]$数组求LMS，求出所有$sum[]$数组最大的那个即可…
不过要注意，由于给出起始与终点位置，所以要记录起始位置，记录方法与上面一样。
eg:
-1 -2 -9 6
8 -9 -3 -6
=>选第1行 sum[0]=[-1,-2,-9,6]
=>选第2行 sum[1]=[8,-9,-3,-6]
=>选第12行 sum[2]=[7,-11,-12,0]
然后分别对sum[0],sum[1],sum[2]用DP求LIS，再选出最大那个即可。其思想就是利用矩阵特性，即子矩阵中每一行等宽，枚举上下边加和成一维，将行列分开计算，实现降维为一维LMS问题：
def getMaxMatrix(self, matrix: List[List[int]]) -> List[int]:
n = len(matrix)
m = len(matrix[0])
sum_matrix = []
row_info = [] #用于记录sum_matrix每一项对应的加法组合的行的起点和终点
#降维存入sum数组
#【错误点】通过双端指针枚举完所有组合法
for i in range(n):
for j in range(i+1,n+1): #错误点：注意这里应该从i+1起始
new = [0]*m
for k in range(i,j):
for l in range(m):
new[l] += matrix[k][l]
sum_matrix.append(new)
row_info.append((i,j-1))
#对sum中的每一个子串使用LMS求(最大值,起点,终点），记录在LMS_max中
LMS_max = []
for i in range(len(sum_matrix)):
nums = sum_matrix[i]
dp = [0]*m
dp[0] = (nums[0],0,0)
for j in range(1,m):
if dp[j-1][0]>0:
dp[j] = (dp[j-1][0]+nums[j],dp[j-1][1],j)
else:
dp[j] = (nums[j],j,j)
list_res = (float('-inf'),0,0)
for k in range(0,m):
if dp[k][0]>list_res[0]:
list_res = dp[k]
LMS_max.append(list_res)
#寻找最大那个
max_res = float('-inf')
index = -1
for i in range(len(sum_matrix)):
if LMS_max[i][0]>max_res:
max_res = LMS_max[i][0]
index = i
return [row_info[index][0],LMS_max[index][1],row_info[index][1],LMS_max[index][2]]答案是对的，但是部分答案OOT了，这不科学…
反正思路就是这个思路了，时间哪里应该还能优化，下次补充
