python - 如何找到值按行和列排序的最大子矩阵？

Question

给定一个矩阵，例如:

[[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。

Answer 1

您可以使用递归来获得适合给定行段下方的最大化区域，该行段本身已被验证为非递减值序列。找到的区域将保证在给定行段的列范围内，但可以更窄并跨越给定行下方的几行。

返回的区域可以向上扩展一行，宽度为该区域已有的宽度。如果该段不能更宽，那么我们将找到可以由该段(或完整段)的子序列与其下方的行组合而成的最大面积。

通过从为所有行的所有段检索的结果中筛选出最佳结果，我们将找到解决方案。

为了避免重复已经对完全相同的段进行的递归计算，可以使用内存(直接编程)。

这里是建议的代码:

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)