最大子矩陣
1,借助最大連續子序列和來取得最大子矩陣
def MaxSubArray(nums):
n = len(nums)
dp = []
dp.append(nums[0])
mymax = dp[0]
startidx = 0
endidx = 0
for i in range(1, n):
if dp[i-1] + nums[i] <= nums[i] and dp[i-1] + nums[i] > 0:
# print "startidx:%d" % i
startidx = i
dp.append(max(dp[i-1] + nums[i], nums[i]))
if dp[i] > mymax:
# print "endidx:%d" % i
endidx = i
mymax = max(dp[i], mymax)
# print mymax
return mymax, startidx, endidx
def MaxSubMatrix(mymatrix):
row = len(mymatrix)
col = len(mymatrix[0])
# 回圈外層
# 固定外層i
# 回圈內層j
# 找出該矩陣中最大的 子矩陣
row_min,row_max,col_min,col_max = (0,0,0,0)
mymax = 0
for row_i in range(row):
# print row_i
for row_j in range(row_i, row):
# print row_j
numlist = []
for col_i in range(col):
# print col_i
num = 0
for row_tmp in range(row_i, row_j + 1):
num += mymatrix[row_tmp][col_i]
numlist.append(num)
tmpmax,startidx,endidx = MaxSubArray(numlist)
if tmpmax > mymax:
mymax = tmpmax
row_min = row_i
row_max = row_j
col_min = startidx
col_max = endidx
print "mymax:%s,row_min:%s,row_max:%s,tartidx:%s,endidx:%s" % (mymax,row_min,row_max,startidx,endidx)
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/74630.html
標籤：其他
上一篇：最大子陣列兩種解法
下一篇：istio 常見的 10 個例外