算法框架 左右剪枝 for(left- 1; left < U; left ++ 利用矩阵左右列关系联系剪枝: 类到的为置歌(都小泡经限到的 for(right- left; right oU & right-left+1 <100; 数《好 算出每一行的最大最小值妆举上下边界求最大子矩 额金會图9是被到 上下剪枝 进一步上下剪枝方法 利用矩阵上下行关系剪枝 处理到当前行 前行不是第 且当前行的 间完全包 ◆如果发现与前面已经得到的子矩阵不能形 成符合条件的子矩阵 则把前面子矩阵中前驱的不符合条件的行 去掉,形成新的包含当前行的符合条件的 如何有效确定上下界 1156算法分析 ◆常量C的取值范围是【0,10】 ◆复杂度n^4但是通过剪枝实际 ◆利用一个数组来记录在该左右边界下,每 的程序比较快 行最高海拔和最低海拔 ◆利用海拔高度进一步剪枝,可 以做到复杂度n^3.10 算法框架 for (left = 1; left <= U; left ++) { for (right = left; right <= U && right – left + 1 <= 100; right ++) { 算出每一行的最大最小值,枚举上下边界求最大子矩 阵; } } 左右剪枝 利用矩阵左右列关系联系剪枝： Š 1、如果以某列为左边界，不考虑海拔限制的情 况下可以求到的最大面积都小于已经求到的最 大面积，则跳出循环。 Š 2、如果当前区间在上一次可以取到的最大连续 的高度与不考虑海拔可以取到的最大宽的乘积 不大于已经求到的最大面积，则跳出循环。 Š 3、如果上次求到的可以取到的最大连续的高度 与当前区间宽度的乘积小于等于已经求到的最 大面积，则直接越过当前循环。 上下剪枝 利用矩阵上下行关系剪枝： 1、如果当前行不是第一行，并且当前行的 海拔区间完全包含上一行的海拔区间，则 显然当前行不可能构成从上一行开始枚举 的面积，直接越过当前循环 。 进一步上下剪枝方法 处理到当前行 Š 如果发现与前面已经得到的子矩阵不能形 成符合条件的子矩阵 Š 则把前面子矩阵中前驱的不符合条件的行 去掉，形成新的包含当前行的符合条件的 子矩阵 如何有效确定上下界 Š 常量C的取值范围是【0，10】 Š 利用一个数组来记录在该左右边界下，每 行最高海拔和最低海拔。 1156算法分析 Š 复杂度n^4,但是通过剪枝,实际 的程序比较快. Š 利用海拔高度进一步剪枝，可 以做到复杂度n^3