提取满足R×R最小尺寸的最大非NaN子矩阵：覆盖最多已知元素

需求说明 #

给定任意维度的矩阵，其某条反对角线下方的所有元素均为未知的NaN。需要从矩阵中提取不含NaN值的子矩阵，需满足以下要求：

• 子矩阵的尺寸尽可能大
• 覆盖原矩阵中尽可能多的已知元素
• 每个子矩阵的尺寸至少为用户指定的R×R
• 子矩阵之间允许重叠

已确定该反对角线的位置，但尚未找到合适的非NaN区域划分方案。当R=3时，存在一种可行的子矩阵划分方式（将有效区域划分为多个满足尺寸要求的最大可能子矩阵，允许重叠）。

现有实现代码 #

目前有一段Matlab代码尝试解决该问题：

mask = ~isnan(A);
nrKnownElsRow = sum(mask,2);
dims = [[1:length(nrKnownElsRow)]' nrKnownElsRow];
dims(dims(:,2)<R,:) = [];
dims(dims(:,1)<R,:) = [];
idx = find(dims(:,2) == max(dims(:,2)));
dims(idx(1:end-1),:) = [];
dims = [dims(:,1) zeros(length(dims),1) dims(:,2)];

for k = 1:length(dims)-1
    if dims(k,3) - dims(k+1,3) >= R
        dims(k,2) = dims(k+1,3) + 1;
    else
        dims(k,2) = dims(k,3) - R + 1;
    end
end
dims(end,2) = 1;

代码中dims变量的每行对应一个子矩阵，存储内容为子矩阵的终止行、起始列、终止列。当前代码虽能覆盖矩阵的大部分已知元素，但生成的子矩阵未达到「尽可能大」的要求。

内容的提问来源于stack exchange，提问作者Stijn Castelyns