前言刷 OJ 时碰到两道好题一道最大子矩阵和一道删除相邻数字的最大分数。两道题都踩了坑记录一下思路和反思。1. 最大子矩阵和1题目及示例已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵你的任务是找到最大的非空大小至少是 1 * 1子矩阵。比如如下 4 * 4 的矩阵0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2的最大子矩阵是9 2 -4 1 -1 8这个子矩阵的大小是 15。输入描述输入是一个 N * N 的矩阵。第一行给出 N0 N ≤ 100。后面若干行依次给出矩阵中的 N² 个整数整数之间由空白字符分隔。矩阵中整数的范围都在 [−127, 127]。输出描述输出最大子矩阵的大小。示例输入 4 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 输出 152错误思路看见这个题目我一开始的想法是类似一维的最大子数组之和。一维最大子数组之和可以用 Kadane 算法解决也可以用动态规划解决。于是乎我尝试建立一个二维 dp 状态方程给dp[i][j]赋予以第 i 行第 j 列位置结尾时最大子矩阵的和。那么计算 dp[i][j] 时就要关注上方和左方的最大子矩阵和比较三种情况只有上方子矩阵、只有左方子矩阵、以及上方和左方加起来。也有可能三个方向的子矩阵都是负数那只能不包含上方和左方自身 1*1 矩阵就是最大。计算上方和左方子矩阵和类似计算二维前缀和两个方向的子矩阵和相加会重复所以需要减去 dp[i-1][j-1]dp[i][j] max(0, dp[i-1][j] dp[i][j-1] - dp[i-1][j-1]) nums[i][j]错误代码#includeiostream#includevectorusingnamespacestd;intmain(){intn;while(cinn){vectorvectorintnums(n,vectorint(n));vectorvectorintdp(n1,vectorint(n1,0));for(inti0;in;i)for(intj0;jn;j)cinnums[i][j];intansnums[0][0];for(inti1;in;i)for(intj1;jn;j){dp[i][j]max(0,dp[i-1][j]dp[i][j-1]-dp[i-1][j-1])nums[i-1][j-1];ansmax(ans,dp[i][j]);}coutansendl;}return0;}但是这个状态转移方程是错的。问题在于dp[i-1][j] 记录的是以 (i-1, j) 结尾的最大子矩阵和但这个子矩阵的形状是不确定的——它可能从第 3 列开始也可能从第 0 列开始你并不知道。当尝试把它和当前格子 (i, j) 拼接时那个子矩阵可能并不包含第 j 列拼起来根本不是一个合法的矩形。换句话说dp[i][j] 的状态定义丢失了子矩阵的边界信息二维 dp 走不通。3正确思路正确的方法是将二维问题降维成一维然后像解决一维最大子数组之和一样使用 Kadane 算法。关键在于枚举子矩阵的上下边界把上下边界之间的每一列累加成一个一维数组对这个一维数组跑 Kadane。具体步骤枚举子矩阵的上边界 top第 0 行到第 n-1 行对于每个 top枚举下边界 bottom从 top 到第 n-1 行随着 bottom 向下扩展把每一行的元素累加到 col_sum[col] 中——这就把一个二维子矩阵压成了一维数组对 col_sum 数组跑 Kadane 算法求出最大子段和所有 (top, bottom) 组合中的最大值就是答案以示例矩阵为例当 top0, bottom1 时┌────┬────┬────┬────┐ │ 0 │ -2 │ -7 │ 0 │ ← top 0 │ 9 │ 2 │ -6 │ 2 │ ← bottom 1 └────┴────┴────┴────┘ col_sum [9, 0, -13, 2] Kadane → max 9当 top1, bottom3 时┌────┬────┬────┬────┐ │ 9 │ 2 │ -6 │ 2 │ ← top 1 │ -4 │ 1 │ -4 │ 1 │ │ -1 │ 8 │ 0 │ -2 │ ← bottom 3 └────┴────┴────┴────┘ col_sum [4, 11, -10, 1] Kadane → 4 → 15 → 5 → 6 max 15 ← 这就是答案时间复杂度枚举上下边界 O(n²)每次 Kadane O(n)总共 O(n³)。对于 N ≤ 100 来说完全够用。4AC代码#includeiostream#includevector#includealgorithm#includeclimitsusingnamespacestd;intmain(){intn;while(cinn){vectorvectorintmatrix(n,vectorint(n));for(inti0;in;i)for(intj0;jn;j)cinmatrix[i][j];intmax_sumINT_MIN;// 枚举上边界 topfor(inttop0;topn;top){vectorintcol_sum(n,0);// 枚举下边界 bottomfor(intbottomtop;bottomn;bottom){// 将 bottom 行累加到 col_sum 中for(intcol0;coln;col)col_sum[col]matrix[bottom][col];// 对 col_sum 跑 Kadaneintcur_sumcol_sum[0];intcur_maxcol_sum[0];for(intcol1;coln;col){cur_summax(col_sum[col],cur_sumcol_sum[col]);cur_maxmax(cur_max,cur_sum);}max_summax(max_sum,cur_max);}}coutmax_sumendl;}return0;}2. 删除相邻数字的最大分数1题目及示例给定一个长度为 n 的仅包含正整数的数组每次操作你可以选择数组中的任意一个元素 a_i同时数组中所有等于 a_i - 1 和 a_i 1 的元素会被全部移除同时你可以得到 a_i 分。直到所有的元素都被选择或者删除请你计算最多能得到多少分。输入描述第一行输入一个正整数 n第二行输入 n 个数字表示数组的各个元素值。输出描述输出能得到的最大分数。数据范围1 ≤ n ≤ 10^51 ≤ a_i ≤ 10^4。示例 1输入 2 1 2 输出 2 说明直接选择元素 2然后 1 被同时移除。示例 2输入 3 1 2 3 输出 4 说明先选择 3同时 2 被移除再选择 1即得 4 分。示例 3输入 9 1 2 1 3 2 2 2 2 3 输出 10 说明第一步选择一个 2所有 1 和 3 都被移除剩下 [2,2,2,2]依次选择得 10 分。2错误思路我一开始想到使用贪心。比如数组中有一段 […, 1, 2, 3, …]去掉 2 得 2 分去掉 1 和 3 得 4 分谁的分高用谁。可是数组如果是 [1, 2, 3, 4]一开始选择去掉 1 和 3那 4 也受影响被删除因为 4 31总得分只有 4。但实际上选 2 和 4 能得 6 分分数更高。贪心行不通的原因一个选择会连锁影响后续的选择范围局部最优不等于全局最优。我的代码只过了 10% 的测试用例。3正确思路如果做过打家劫舍类型的 dp 题你就会敏锐地发现打家劫舍问题中选择打劫这家就不能打劫隔壁家。这道题也一样——选择数字 xx-1 和 x1 就不能选了。回到题目本身假设选择了 xx 的出现次数为 cnt[x]那么得分就是 x * cnt[x]因为所有等于 x 的元素都会被选掉。x-1 和 x1 的元素会被删除但不得分。所以我们把原数组转换成一个按值域排列的数组 total[]其中 total[x] x * cnt[x]表示选择数字 x 能获得的总分。接下来就是标准的打家劫舍 dp令 dp[i] 表示在数字 1 到 i 中能获得的最高分不选 idp[i] dp[i-1]选 idp[i] dp[i-2] total[i]选了 ii-1 会被删除所以看 i-2 的状态状态转移方程dp[i] max(dp[i-1], dp[i-2] total[i])以示例 3 为例原数组1 2 1 3 2 2 2 2 3 统计次数cnt[1]2, cnt[2]5, cnt[3]2 total 数组total[x] x * cnt[x] 下标: 0 1 2 3 total: 0 2 10 6 dp 过程 dp[0] 0 dp[1] max(0, total[1]) 2 → 选 1 dp[2] max(dp[1], dp[0]total[2]) max(2, 10) 10 → 选 2 dp[3] max(dp[2], dp[1]total[3]) max(10, 8) 10 → 不选 3 答案dp[3] 104AC代码#includeiostream#includevector#includealgorithmusingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn;if(!(cinn))return0;vectorintnums(n);intmax_val0;for(inti0;in;i){cinnums[i];max_valmax(max_val,nums[i]);}// 统计每个数字的总分total[x] x * cnt[x]vectorlonglongtotal(max_val2,0);for(intx:nums)total[x]x;// dp[i] 表示处理到数字 i 时能获得的最大分数vectorlonglongdp(max_val2,0);dp[0]0;dp[1]max(0LL,total[1]);for(inti2;imax_val;i)dp[i]max(dp[i-1],dp[i-2]total[i]);coutdp[max_val]endl;return0;}3. 总结题目1看见类似一维的题目就硬往二维 dp 推想着用 O(n²) 解决结果钻了牛角尖。dp[i][j] 的状态定义丢失了子矩阵的边界信息拼接时无法保证矩形性。这提醒我遇到新题先想暴力解法——枚举上下边界再跑 Kadane 是 O(n³)虽然不够优但至少是对的。先对再优化。题目2一开始陷入贪心思路局部最优不等于全局最优。其实已经联想到打家劫舍了但觉得转换复杂就没敢尝试。大胆假设小心求证创作充满挑战但若我的文章能为你带来一丝启发或帮助那便是我最大的荣幸。如果你喜欢这篇文章请不吝点赞、评论和分享你的支持是我继续创作的最大动力