2026-08-30：矩阵中最大共享路径和。用go语言，有一个 m 行 n 列的整数矩阵。 第一个玩家从矩阵的左上角出发，只能向右或向下走，最终要

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的段）。

因此：

• • 如果共享段是水平的，那么它就是某一行中连续的一段。

• • 如果共享段是垂直的，那么它就是某一列中连续的一段。

于是问题变成：

在矩阵中，找出所有可能作为共享段的水平连续段或垂直连续段，计算它们的和，取最大值。

• • 功能：计算一个数组中长度至少为 2的连续子数组的最大和。

• • 实现方式：

• • • 用动态规划，f表示以当前元素结尾的最大子数组和（允许长度为1）。

  • • 但是，为了强制长度 ≥ 2，它每次用f + x来更新答案，这保证至少有两个数。

  • • 再更新f = max(f, 0) + x，相当于允许从当前元素重新开始（但用于后续组合）。

步骤 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完整代码如下：

package main

 import (
    "fmt"
    "math"
    "slices"
)

 func maxSubArray(nums []int) int {
    ans := math.MinInt // 注意答案可以是负数，不能初始化成 0
    f := nums[0]
    for _, x := range nums[1:] {
        ans = max(ans, f+x) // f+x 保证子数组至少有两个数
        f = max(f, 0) + x
    }
    return ans
}

 func maxScore(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    ans := math.MinInt

     // 单独计算子数组长为 1 的情况，此时子数组不能在 grid 的边界上
    if m > 2 && n > 2 {
        for _, row := range grid[1 : m-1] {
            ans = max(ans, slices.Max(row[1:n-1]))
        }
    }

     // 每行的最大子数组和（子数组长度 >= 2）
    for _, row := range grid {
        ans = max(ans, maxSubArray(row))
    }

     // 每列的最大子数组和（子数组长度 >= 2）
    col := make([]int, m)
    for j := range n {
        for i, row := range grid {
            col[i] = row[j]
        }
        ans = max(ans, maxSubArray(col))
    }

     return ans
}

 func main() {
    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-*-

 import math
from typing import List

 def max_sub_array(nums: List[int]) -> int:
    # 注意答案可以是负数，不能初始化成 0
    ans = -math.inf
    f = nums[0]
    for x in nums[1:]:
        # f+x 保证子数组至少有两个数
        ans = max(ans, f + x)
        f = max(f, 0) + x
    return ans

 def max_score(grid: List[List[int]]) -> int:
    m, n = len(grid), len(grid[0])
    ans = -math.inf

     # 单独计算子数组长为 1 的情况，此时子数组不能在 grid 的边界上
    if m > 2 and n > 2:
        for row in grid[1:m-1]:
            # 注意切片是左闭右开，row[1:n-1] 会排除第一列和最后一列
            if row[1:n-1]:
                ans = max(ans, max(row[1:n-1]))

     # 每行的最大子数组和（子数组长度 >= 2）
    for row in grid:
        ans = max(ans, max_sub_array(row))

     # 每列的最大子数组和（子数组长度 >= 2）
    for j in range(n):
        col = [grid[i][j] for i in range(m)]
        ans = max(ans, max_sub_array(col))

     return ans

 if __name__ == "__main__":
    grid = [
        [1, 2, 0, -3],
        [1, -2, 1, 0],
        [-4, 2, -1, 3],
        [3, -3, 3, -2],
        [-1, -5, 0, 1]
    ]
    result = max_score(grid)
    print(result)

C++完整代码如下：

  

  

    


 using namespace std;

 int maxSubArray(const vector& nums) {
    // 注意答案可以是负数，不能初始化成 0
    int ans = INT_MIN;
    int f = nums[0];
    for (size_t i = 1; i < nums.size(); i++) {
        int x = nums[i];
        // f+x 保证子数组至少有两个数
        ans = max(ans, f + x);
        f = max(f, 0) + x;
    }
    return ans;
}

 int maxScore(const vector 
 
 int 
 >>& grid) { 
 
 
      
 int 
  m = grid.size(); 
 
 
      
 int 
  n = grid[ 
 0 
 ].size(); 
 
 
      
 int 
  ans = INT_MIN; 
 
 
 
 
      
 // 单独计算子数组长为 1 的情况，此时子数组不能在 grid 的边界上 
 
 
      
 if 
  (m >  
 2 
  && n >  
 2 
 ) { 
 
 
          
 for 
  ( 
 int 
  i =  
 1 
 ; i < m -  
 1 
 ; i++) { 
 
 
              
 // 找到 row[1:n-1] 中的最大值 
 
 
              
 int 
  maxVal = INT_MIN; 
 
 
              
 for 
  ( 
 int 
  j =  
 1 
 ; j < n -  
 1 
 ; j++) { 
 
 
                 maxVal = max(maxVal, grid[i][j]); 
 
 
             } 
 
 
             ans = max(ans, maxVal); 
 
 
         } 
 
 
     } 
 
 
 
 
      
 // 每行的最大子数组和（子数组长度 >= 2） 
 
 
      
 for 
  ( 
 const 
  auto& row : grid) { 
 
 
         ans = max(ans, maxSubArray(row)); 
 
 
     } 
 
 
 
 
      
 // 每列的最大子数组和（子数组长度 >= 2） 
 
 
     vector< 
 int 
 > col(m); 
 
 
      
 for 
  ( 
 int 
  j =  
 0 
 ; j < n; j++) { 
 
 
          
 for 
  ( 
 int 
  i =  
 0 
 ; i < m; i++) { 
 
 
             col[i] = grid[i][j]; 
 
 
         } 
 
 
         ans = max(ans, maxSubArray(col)); 
 
 
     } 
 
 
 
 
      
 return 
  ans; 
 
 
 } 
 
 
 
 
 int 
  main() { 
 
 
     vector 
 
 int 
 >> grid = { 
 
 
         { 
 1 
 ,  
 2 
 ,  
 0 
 ,  
 -3 
 }, 
 
 
         { 
 1 
 ,  
 -2 
 ,  
 1 
 ,  
 0 
 }, 
 
 
         { 
 -4 
 ,  
 2 
 ,  
 -1 
 ,  
 3 
 }, 
 
 
         { 
 3 
 ,  
 -3 
 ,  
 3 
 ,  
 -2 
 }, 
 
 
         { 
 -1 
 ,  
 -5 
 ,  
 0 
 ,  
 1 
 } 
 
 
     }; 
 
 
      
 int 
  result = maxScore(grid); 
 
 
     cout << result << endl; 
 
 
      
 return 
   
 0 
 ; 
 
 
 } 
 
 
 
 

我们相信人工智能为普通人提供了一种“增强工具”，并致力于分享全方位的AI知识。在这里，您可以找到最新的AI科普文章、工具评测、提升效率的秘籍以及行业洞察。 欢迎关注“福大大架构师每日一题”，发消息可获得面试资料，让AI助力您的未来发展。