2026-08-30矩阵中最大共享路径和。用go语言有一个 m 行 n 列的整数矩阵。第一个玩家从矩阵的左上角出发只能向右或向下走最终要走到右下角。第二个玩家从左下角出发只能向右或向上走最终要走到右上角。每个玩家各自选一条符合自己移动规则的完整路线。如果某个格子同时被这两个玩家选中的路线经过就称它为“共享格子”。现在请你计算在所有可能的路线组合中所有共享格子上的数值之和最大可以达到多少。最后返回这个最大总和值。m grid.length。n grid[i].length。2 m, n 1000。4 m * n 500000。-100 grid[i][j] 100。输入 grid [[1,2,0,-3],[1,-2,1,0],[-4,2,-1,3],[3,-3,3,-2],[-1,-5,0,1]]。输出 4。解释图中展示了一种最优路径选择。玩家 1 沿着从左上角到右下角的红色/紫色路径移动(0, 0) → (1, 0) → (2, 0) → (2, 1) → (2, 2) → (2, 3) → (3, 3) → (4, 3)玩家 2 沿着从左下角到右上角的蓝色/紫色路径移动(4, 0) → (4, 1) → (3, 1) → (2, 1) → (2, 2) → (2, 3) → (1, 3) → (0, 3)共享单元格为 (2, 1) 、(2, 2) 和 (2, 3) 。总和为 2 (-1) 3 4 这是可能的最大总和。题目来自力扣3938。一、题目核心理解两个玩家路径形状不同玩家1左上 → 右下只能右/下玩家2左下 → 右上只能右/上两条路径共享的格子它们的值会被加总。我们要找所有可能路径组合中共享格子值之和的最大值。二、算法整体思路根据代码推导代码并没有直接模拟两条路径而是将问题转化为“寻找矩阵中某个方向上的最大子数组和”这一点需要先说明关键观察隐含的数学性质对于这种“一个从左上到右下一个从左下到右上”的路径它们共享的格子一定形成一条连续的水平或垂直段因为移动方向限制。具体地在这个 4 方向限制下两条路径的交集要么是一条水平连续段要么是一条垂直连续段也可能只是一个点但单点可视为长度为1的段。因此如果共享段是水平的那么它就是某一行中连续的一段。如果共享段是垂直的那么它就是某一列中连续的一段。于是问题变成在矩阵中找出所有可能作为共享段的水平连续段或垂直连续段计算它们的和取最大值。三、代码对应步骤分解1. 定义辅助函数maxSubArray(nums)功能计算一个数组中长度至少为 2的连续子数组的最大和。实现方式用动态规划f表示以当前元素结尾的最大子数组和允许长度为1。但是为了强制长度 ≥ 2它每次用f x来更新答案这保证至少有两个数。再更新f max(f, 0) x相当于允许从当前元素重新开始但用于后续组合。2. 主函数maxScore(grid)处理过程步骤 2.1 – 初始化获取行数m、列数n。答案ans初始为极小值负无穷。步骤 2.2 – 处理长度为 1 的共享段单格子条件m 2 n 2即矩阵内部有非边界格子。遍历所有不在最外圈的格子行 1 到 m-2列 1 到 n-2。对于这些格子单独取它的值作为长度为1的共享段更新ans。为什么只取内部因为边界格子不可能成为两条路径的唯一共享点路径起始或终点本身虽可共享但题目隐含最大和不会只取边界单点且代码特意排除。步骤 2.3 – 处理水平共享段长度 ≥ 2遍历每一行。对每一行调用maxSubArray计算该行中长度 ≥ 2 的最大连续子数组和。更新ans。步骤 2.4 – 处理垂直共享段长度 ≥ 2对每一列提取该列所有元素组成一个长度为m的临时数组col。对该数组调用maxSubArray得到该列中长度 ≥ 2 的最大连续子数组和。更新ans。步骤 2.5 – 返回答案返回最终ans。四、关于为什么这样能覆盖所有情况简要解释两条路径的交集由于移动方向限制确实只会是一条水平或垂直的连续段。段的长度可以是 1 或多个格子。代码分别覆盖了长度为1仅内部格子长度≥2按行或按列求最大子数组和因此它能找到所有可能的共享段的最大和。五、时间复杂度和空间复杂度时间复杂度行扫描对每一行调用maxSubArray每行长度 n共 m 行 →O(m·n)列扫描对每一列构造长度为 m 的数组共 n 列 →O(n·m)单格子扫描最多 (m-2)·(n-2) 个 → 也是O(m·n)总体O(m·n)额外空间复杂度仅用了一个长度为m的临时数组col用于提取列。其余为常数变量。因此额外空间为O(m)因为列长度最大为 m。六、总结算法本质将二维路径共享问题降维成一维最大子数组问题。分三类情况处理共享段单点、水平段、垂直段。时间复杂度O(m·n)空间复杂度O(m)或 O(min(m,n))这里取 O(m)。如果你还想进一步了解为什么两条路径的交集一定只是水平或垂直连续段我可以画图或给出更直观的证明。Go完整代码如下packagemainimport(fmtmathslices)funcmaxSubArray(nums[]int)int{ans:math.MinInt// 注意答案可以是负数不能初始化成 0f:nums[0]for_,x:rangenums[1:]{ansmax(ans,fx)// fx 保证子数组至少有两个数fmax(f,0)x}returnans}funcmaxScore(grid[][]int)int{m,n:len(grid),len(grid[0])ans:math.MinInt// 单独计算子数组长为 1 的情况此时子数组不能在 grid 的边界上ifm2n2{for_,row:rangegrid[1:m-1]{ansmax(ans,slices.Max(row[1:n-1]))}}// 每行的最大子数组和子数组长度 2for_,row:rangegrid{ansmax(ans,maxSubArray(row))}// 每列的最大子数组和子数组长度 2col:make([]int,m)forj:rangen{fori,row:rangegrid{col[i]row[j]}ansmax(ans,maxSubArray(col))}returnans}funcmain(){grid:[][]int{{1,2,0,-3},{1,-2,1,0},{-4,2,-1,3},{3,-3,3,-2},{-1,-5,0,1}}result:maxScore(grid)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-importmathfromtypingimportListdefmax_sub_array(nums:List[int])-int:# 注意答案可以是负数不能初始化成 0ans-math.inf fnums[0]forxinnums[1:]:# fx 保证子数组至少有两个数ansmax(ans,fx)fmax(f,0)xreturnansdefmax_score(grid:List[List[int]])-int:m,nlen(grid),len(grid[0])ans-math.inf# 单独计算子数组长为 1 的情况此时子数组不能在 grid 的边界上ifm2andn2:forrowingrid[1:m-1]:# 注意切片是左闭右开row[1:n-1] 会排除第一列和最后一列ifrow[1:n-1]:ansmax(ans,max(row[1:n-1]))# 每行的最大子数组和子数组长度 2forrowingrid:ansmax(ans,max_sub_array(row))# 每列的最大子数组和子数组长度 2forjinrange(n):col[grid[i][j]foriinrange(m)]ansmax(ans,max_sub_array(col))returnansif__name____main__:grid[[1,2,0,-3],[1,-2,1,0],[-4,2,-1,3],[3,-3,3,-2],[-1,-5,0,1]]resultmax_score(grid)print(result)C完整代码如下#includeiostream#includevector#includealgorithm#includeclimitsusingnamespacestd;intmaxSubArray(constvectorintnums){// 注意答案可以是负数不能初始化成 0intansINT_MIN;intfnums[0];for(size_t i1;inums.size();i){intxnums[i];// fx 保证子数组至少有两个数ansmax(ans,fx);fmax(f,0)x;}returnans;}intmaxScore(constvectorvectorintgrid){intmgrid.size();intngrid[0].size();intansINT_MIN;// 单独计算子数组长为 1 的情况此时子数组不能在 grid 的边界上if(m2n2){for(inti1;im-1;i){// 找到 row[1:n-1] 中的最大值intmaxValINT_MIN;for(intj1;jn-1;j){maxValmax(maxVal,grid[i][j]);}ansmax(ans,maxVal);}}// 每行的最大子数组和子数组长度 2for(constautorow:grid){ansmax(ans,maxSubArray(row));}// 每列的最大子数组和子数组长度 2vectorintcol(m);for(intj0;jn;j){for(inti0;im;i){col[i]grid[i][j];}ansmax(ans,maxSubArray(col));}returnans;}intmain(){vectorvectorintgrid{{1,2,0,-3},{1,-2,1,0},{-4,2,-1,3},{3,-3,3,-2},{-1,-5,0,1}};intresultmaxScore(grid);coutresultendl;return0;}