2024-11-12

最大子矩阵

1464055387

问题描述

给定一个n*m的矩阵A，求A中的一个非空子矩阵，使这个子矩阵中的元素和最大。

其中，A的子矩阵指在A中行和列均连续的一块。
输入格式

输入的第一行包含两个整数n, m，分别表示矩阵A的行数和列数。

接下来n行，每行m个整数，表示矩阵A。
输出格式

输出一行，包含一个整数，表示A中最大的子矩阵中的元素和。
样例输入

3 3
-1 -4 3
3 4 -1
-5 -2 8

样例输出

样例说明

取最后一列，和为10。
数据规模和约定

对于50%的数据，1<=n, m<=50；

对于100%的数据，1<=n, m<=500，A中每个元素的绝对值不超过5000。
解题思路

像题目要求最大什么什么，大多都用Dp。其实刚刚接到题目我也有点慌了，自己最不拿手就是Dp，像这道题，矩阵无非就是用一个二维数组存储的数据，

那么先要对矩阵进行压缩，可以以行为主序，也可以以列为主序，拿行来举例

2 5 -1
7 -5 3
0 8 -11

这一组数据，我们很容易可以看出来最大子矩阵是17

2 5
7 -5
0 8

没错，这是一个最大的子矩阵，其实你可以这样去分解他，以行为主序那他就成了

9 8 -8

这不就成了求最大子段问题啦，哈哈，没想到吧

那么就要对他进行压缩了，一开始我没想到有更好的办法，只好每两个列的差值都存储，但后来发现了一个巧妙的方法，那就是取他的行差或者列差

像上面的数据，可以这样进行压缩，就是把每列的值够累计相加，得出以下的数据

2 5 -1
9 0 2
9 8 -8

很容易理解，第一行就是原来矩阵第一行的子矩阵，最后一行就是整个矩阵，第二行就是原来矩阵的第一第二行压缩出来的，如果想得到原来矩阵的第二第三行压缩矩阵，那么拿压缩后的矩阵的第三行减第一行，有没有。哈哈
代码实现

import java.util.Scanner;

/**

最大子矩阵
@author Ape

/
public class MaxJz {

static int[][] a = new int[510][510];
static int n, m, t, sum, max;

public static void main(String[] args) {

Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= m; j++) {
        t = scanner.nextInt();
        a[i][j] = a[i - 1][j] + t; // 压缩矩阵
    }
max = Integer.MIN_VALUE;
for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) {
        sum = 0;
        for (int k = 1; k <= m; k++) {
            t = a[j][k] - a[i - 1][k]; // 计算第i行到第j行的差
            if (sum > 0)
                sum += t;
            else
                sum = t;
            if (sum > max)
                max = sum;
        }
    }
System.out.println(max);
scanner.close();

}

ps:距离第七届蓝桥杯决赛还有3天