「To the Max」最大的和

题目描述

给定 $n \times n$ 整数矩阵（ $n \le 100$ ），求元素和最大的子矩阵的和。

思路

枚举子矩阵的上下边界行，把中间各行按列求和压成一维数组，对一维数组跑 Kadane 最大子段和，取所有上下边界组合的最大值， $O(n^3)$ 。

参考代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 11:03
# update_at: 2026-10-04 11:09

import sys
from itertools import accumulate


def solve() -> None:
    """枚举上下边界，按列求和压成一维，再用 Kadane 求最大子段和。"""
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)  # 题面位置量：矩阵阶数
    a = [[next(data) for _ in range(n)] for _ in range(n)]  # n 行 × n 列，按行顺序消费

    # s[i][c] = 前 i 行第 c 列的元素和，s[0] 全 0 作哨兵
    s = list(accumulate([[0] * n] + a,
                        lambda pre, row: [p + x for p, x in zip(pre, row)]))

    # 固定行区间 [i, j)：第 c 列的竖条和为 s[j][c] - s[i][c]，
    # accumulate 递推 cur = max(cur, 0) + colsum 正是一维 Kadane
    ans = max(
        max(accumulate((s[j][c] - s[i][c] for c in range(n)),
                       lambda cur, x: cur + x if cur > 0 else x))
        for i in range(n) for j in range(i + 1, n + 1)
    )
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 11:20
 * update_at: 2026-10-06 11:22
 */
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

const int MAXN = 105;

ll a[MAXN][MAXN]; // 原矩阵
ll s[MAXN][MAXN]; // s[i][j] 表示前 i 行第 j 列的元素和（列前缀和）

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    // 读入矩阵，同时构建列前缀和：s[i][j] = sum_{r=0}^{i-1} a[r][j]
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            s[i][j] = s[i - 1][j] + a[i][j];
        }
    }

    ll ans = a[1][0]; // 初始答案，至少取一个元素
    // 枚举行界 [u, d]
    for (int u = 1; u <= n; u++) {
        for (int d = u; d <= n; d++) {
            ll cur = 0; // 以当前列结尾的最大子段和
            for (int c = 0; c < n; c++) {
                ll colsum = s[d][c] - s[u - 1][c]; // 第 c 列在行 [u, d] 的竖条和
                // Kadane：若 cur < 0 则丢弃，从当前列重新开始
                if (cur < 0) cur = colsum;
                else cur += colsum;
                if (cur > ans) ans = cur;
            }
        }
    }

    cout << ans << "\n";
    return 0;
}

「To the Max」 最大的和

目录

题目描述

思路

参考代码

「To the Max」最大的和