给定一个矩阵，例如:
[[2 5 3 8 3]
[1 4 6 8 4]
[3 6 7 9 5]
[1 3 6 4 2]
[2 6 4 3 1]]
...如何找到所有行都排序且所有列都排序的最大子矩阵(即具有最多值)？
在上面的例子中，解是 (1,0)-(2,3) 处的子矩阵:
1 4 6 8
3 6 7 9
它的大小是 8。
最佳答案
您可以使用递归来获得适合给定行段下方的最大化区域，该行段本身已被验证为非递减值序列。找到的区域将保证在给定行段的列范围内，但可以更窄并跨越给定行下方的几行。
返回的区域可以向上扩展一行，宽度为该区域已有的宽度。如果该段不能更宽，那么我们将找到可以由该段(或完整段)的子序列与其下方的行组合而成的最大面积。
通过从为所有行的所有段检索的结果中筛选出最佳结果，我们将找到解决方案。
为了避免重复已经对完全相同的段进行的递归计算，可以使用内存(直接编程)。
这里是建议的代码:
from collections import namedtuple
Area = namedtuple('Area', 'start_row_num start_col_num end_row_num end_col_num size')
EMPTY_AREA = Area(0,0,0,0,0)
def greatest_sub(matrix):
memo = {}
# Function that will be called recursively
def greatest_downward_extension(row_num, start_col_num, end_col_num, depth=0):
# Exit if the described segment has no width
if end_col_num <= start_col_num:
return EMPTY_AREA
next_row_num = row_num + 1
# Use memoisation:
# Derive an ID (hash) from the segment's attributes for use as memoisation key
segment_id = ((row_num * len(matrix[0]) + start_col_num)
* len(matrix[0]) + end_col_num)
if segment_id in memo:
return memo[segment_id]
# This segment without additional rows is currently the best we have:
best = Area(row_num, start_col_num, next_row_num, end_col_num,
end_col_num - start_col_num)
if next_row_num >= len(matrix):
return best
next_row = matrix[next_row_num]
row = matrix[row_num]
prev_val = -float('inf')
for col_num in range(start_col_num, end_col_num + 1):
# Detect interruption in increasing series,
# either vertically (1) or horizontally (0)
status = (1 if col_num >= end_col_num or next_row[col_num] < row[col_num]
else (0 if next_row[col_num] < prev_val
else -1))
if status >= 0: # There is an interruption: stop segment
# Find largest area below current row segment, within its column range
result = greatest_downward_extension(next_row_num,
start_col_num, col_num)
# Get column range of found area and add that range from the current row
size = result.size + result.end_col_num - result.start_col_num
if size > best.size:
best = Area(row_num, result.start_col_num,
result.end_row_num, result.end_col_num, size)
if col_num >= end_col_num:
break
# When the interruption was vertical, the next segment can only start
# at the next column (status == 1)
start_col_num = col_num + status
prev_val = row[col_num]
memo[segment_id] = best
return best
# For each row identify the segments with non-decreasing values
best = EMPTY_AREA
for row_num, row in enumerate(matrix):
prev_val = -float('inf')
start_col_num = 0
for end_col_num in range(start_col_num, len(row) + 1):
# When value decreases (or we reached the end of the row),
# the segment ends here
if end_col_num >= len(row) or row[end_col_num] < prev_val:
# Find largest area below current row segment, within its column range
result = greatest_downward_extension(row_num, start_col_num, end_col_num)
if result.size > best.size:
best = result
if end_col_num >= len(row):
break
start_col_num = end_col_num
prev_val = row[end_col_num]
return best
# Sample call
matrix = [
[2, 5, 3, 8, 3],
[1, 4, 6, 8, 4],
[3, 6, 7, 9, 5],
[1, 3, 6, 4, 2],
[2, 6, 4, 3, 1]]
result = greatest_sub(matrix)
print(result)
示例数据的输出将是:
Area(start_row_num=1, start_col_num=0, end_row_num=3, end_col_num=4, size=8)
关于python - 如何找到值按行和列排序的最大子矩阵？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47229802/