Meta 网格最大表达式：固定方向与合法终点

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 每格是单个ASCII数字或+/-；不能连接成多位数，不能转弯，表达式必须以数字开头和结束。单数字是合法表达式。
• 可在任意合法数字终点停止，不必走到边缘；没有数字则返回None。空矩阵或非矩形拒绝。

解题路线

1. 枚举每个数字起点及两个方向。初值为首数字；接下来成对读取operator和digit，只有两格都合法才累计。每到数字终点更新best。
2. 遇连续数字、连续运算符或边界，当前方向无法继续，但此前合法前缀仍有效。不能把所有格拼接后只算最长字符串。
3. 加减同优先级且无括号，从左到右累计即可；−号不表示路径反向，不允许起点选−形成负单数。

手动走一遍

一行["8−9+7"]：从8开始的合法前缀值8/−1/6；从9开始可得9/16，所以最大16。该例说明必须允许中途起点，也不能只比较整行6。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

def maximum_straight_expression(grid):
    """Single digit, +, -; choose any digit start and a nonempty straight right/down expression."""
    if not grid or not grid[0] or any(len(row)!=len(grid[0]) for row in grid):
        raise ValueError("nonempty rectangle required")
    if any(c not in '0123456789+-' for row in grid for c in row):
        raise ValueError("single ASCII digit or +/- required")
    h,w=len(grid),len(grid[0]);best=None
    for r in range(h):
        for c in range(w):
            if grid[r][c] not in '0123456789':continue
            for dr,dc in ((0,1),(1,0)):
                total=ord(grid[r][c])-ord('0');best=total if best is None else max(best,total)
                rr,cc=r+dr,c+dc
                while 0<=rr<h and 0<=cc<w:
                    op=grid[rr][cc]
                    nr,nc=rr+dr,cc+dc
                    if op not in '+-' or not(0<=nr<h and 0<=nc<w) or grid[nr][nc] not in '0123456789':break
                    value=ord(grid[nr][nc])-ord('0')
                    total += value if op=='+' else -value
                    best=max(best,total)
                    rr,cc=nr+dr,nc+dc
    return best

复杂度

基线枚举所有起点和最长射线，O(HW(H+W))时间、O(1)额外状态；输入已存在。若规模大，可沿每行/列构建交替段并做前缀差优化，需限定起终点 parity后证明。

易错点与追问

容易失分的边界

• 转弯会生成题面不允许的表达式；普通网格DFS的路径集合过大且语义错。
• 最后字符是运算符的前缀不合法，不能直接eval。

继续深挖

• 若新增乘法，需要处理优先级状态，而非简单累计；若允许转弯，路径是否能重访决定有环优化模型。
• 若返回表达式和坐标，记录最优起点/方向/长度，仍不需复制每条路径。