C++实现：优化算法求最大全1正方形

"算法趣味性C++课程探讨了一道有趣的问题：在一个n*n的格子中，每个单元格只有0或1，目标是找到一个最大的全为1的正方形。这个问题起初可以通过朴素的算法解决，即遍历每个点并检查以该点为中心、边长从1到n的所有可能正方形是否全为1，这将导致O(n^5)的时间复杂度。 然而，通过观察和分析，可以对算法进行优化。首先，注意到全为1的正方形所有元素之和等于边长的平方（例如，3x3的正方形和为9）。因此，我们可以通过预先计算每个位置的子矩阵和（sum[i][j]）来快速判断一个子区域的和是否符合边长要求。这样，我们可以用O(n^2)的时间复杂度计算出每个点周围的所有子正方形的和，然后只需O(1)时间进行比较，从而降低到O(n^3)的整体复杂度。 具体步骤包括： 1. 初始化一个二维数组sum，记录每个位置的子矩阵和。 2. 对于每个点(x, y)，计算以它为左上角的子矩阵和sum[i][j]，其中i和j分别表示行和列。 3. 检查sum[side][side]是否等于side^2，如果不是，则该正方形不是全1的。 4. 如果sum[side][side]匹配，递归地检查右下角点的和减去边界值（sum[side][y], sum[x][side], sum[side][side] - sum[x][y]），以确定是否有更大的正方形。 举例来说，如图所示的5x5矩阵： ``` 111001 111001 111111 011111 101111 101111 ``` 要检查point(3,3)处边长为3的正方形，我们可以查看sum[5][5]（19），然后减去sum[2][5]（6）、sum[5][2]（6）以及sum[2][2]（1），结果为6，这表明该子正方形不是全1的。 通过这样的优化，我们降低了算法的复杂度，使得在实际问题中，当n较大时，解决方案更为高效。这展示了算法设计中的一个重要原则：通过巧妙的数据结构和预处理，可以显著提升算法性能，使我们在面对复杂问题时保持计算效率。"