题解 | 最大子矩阵

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int N = in.nextInt();
        int[][] matrix = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                matrix[i][j] = in.nextInt();
            }
        }
        
        int[][] prefixSum = new int[N][N];
        for (int c = 0; c < N; c++) {
            prefixSum[0][c] = matrix[0][c];
            for (int r = 1; r < N; r++) {
                prefixSum[r][c] = prefixSum[r-1][c] + matrix[r][c];
            }
        }
        
        int maxSum = Integer.MIN_VALUE;
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                int currentMax;
                int maxSub;
                int sum;
                if (i == 0) {
                    sum = prefixSum[j][0];
                } else {
                    sum = prefixSum[j][0] - prefixSum[i-1][0];
                }
                currentMax = sum;
                maxSub = sum;
                for (int c = 1; c < N; c++) {
                    if (i == 0) {
                        sum = prefixSum[j][c];
                    } else {
                        sum = prefixSum[j][c] - prefixSum[i-1][c];
                    }
                    currentMax = Math.max(sum, currentMax + sum);
                    maxSub = Math.max(maxSub, currentMax);
                }
                if (maxSub > maxSum) {
                    maxSum = maxSub;
                }
            }
        }
        System.out.println(maxSum);
    }
}

https://www.nowcoder.com/discuss/727521113110073344

思路：

1. 输入处理：读取矩阵的维度和元素。
2. 前缀和数组计算：构建每一列的前缀和数组，以便快速计算任意行区间内的列和。
3. 遍历行组合：遍历所有可能的行起始和结束组合(i, j)。
4. 列和计算与Kadane算法应用：对于每个行组合，计算对应的列和数组，并使用Kadane算法找到最大子数组和，从而确定当前行组合的最大子矩阵和。
5. 全局最大值更新：维护一个全局最大值，不断更新以找到所有行组合中的最大子矩阵和。