DP $O(n^3)$

要点

1. 前置题型：AcWing 55. 连续子数组的最大和（Java DP 求位置连续的子序列最大和），由一维的位置连续子序列扩展到二维，区别在于有了上下界的限制，且单个元素变为整列之和
2. 上下界可以枚举，复杂度$O(n^2)$；整列之和可以优化为使用列方向的前缀和求部分和

步骤

1. 读入数字，求列方向前缀和
2. 两层循环分别枚举上界和下界
3. 第三次循环，求“只考虑当前上下界中前$i$列且以第$i$列结尾的子矩阵的选法集合”
   • 属性：总和$Max$
   • 状态计算：$f(i) = max(0, f(i-1)) + \sum_{j=up}^{down} a(j,i)$
4. 注意更新最终答案，且每次上下界改变时重置状态$f$

代码

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, N = 110;
    static int[][] s = new int[N][N];

    public static void main(String[] args) {
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                s[i][j] = s[i - 1][j] + scanner.nextInt();
            }
        }

        int res = Integer.MIN_VALUE;
        for (int up = 1; up <= n; up++) {
            for (int down = up; down <= n; down++) {
                int f = 0;
                for (int col = 1; col <= n; col++) {
                    f = Math.max(0, f) + (s[down][col] - s[up - 1][col]);
                    res = Math.max(res, f);
                }
            }
        }
        System.out.println(res);
    }
}

暴力枚举 $O(n^4)$

要点

1. 考虑每个子矩阵，并计算矩阵元素之和，取最大值
2. 通过左上角坐标$(x_1,y_1)$和右下角坐标$(x_2,y_2)$枚举所有子矩阵，共四层循环
3. 借助矩阵前缀和求部分和得到子矩阵元素总和

代码

import java.util.*;
import java.lang.*;

public class Main {
    static Scanner scanner = new Scanner(System.in);

    static int n, N = 110;
    static int[][] a = new int[N][N], s = new int[N][N];

    static int getSum(int x1, int y1, int x2, int y2) {
        return s[x2][y2] - s[x2][y1 - 1] - s[x1 - 1][y2] + s[x1 - 1][y1 - 1];
    }

    public static void main(String[] args) {
        n = scanner.nextInt();
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                a[i][j] = scanner.nextInt();
                s[i][j] = s[i][j - 1] + s[i - 1][j] - s[i - 1][j - 1] + a[i][j];
            }
        }
        int res = Integer.MIN_VALUE;
        for (int x1 = 1; x1 <= n; x1++) {
            for (int y1 = 1; y1 <= n; y1++) {
                for (int x2 = x1; x2 <= n; x2++) {
                    for (int y2 = y1; y2 <= n; y2++) {
                        res = Math.max(res, getSum(x1, y1, x2, y2));
                    }
                }
            }
        }
        System.out.println(res);
    }
}