202630：矩阵中最大共享路径和。用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的段）。

因此：

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

于是问题变成：

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

三、代码对应步骤分解

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

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

#include 
#include 
#include 
#include 

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>& 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 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> 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;
}