每日OJ题_牛客_DP10最大子矩阵_二维前缀和_C++_Java

目录

牛客_DP10最大子矩阵_二维前缀和

题目解析

C++代码

Java代码

牛客_DP10最大子矩阵_二维前缀和

最大子矩阵_牛客题霸_牛客网 (nowcoder.com)

描述：

        已知矩阵的大小定义为矩阵中所有元素的和。给定一个矩阵，你的任务是找到最大的非空(大小至少是1 * 1)子矩阵。 比如，如下4 * 4的矩阵 0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -1 8 0 -2 的最大子矩阵是 9 2 -4 1 -1 8 这个子矩阵的大小是15。

输入描述：

        输入是一个N * N的矩阵。输入的第一行给出N (0 < N <= 100)。 再后面的若干行中，依次（首先从左到右给出第一行的N个整数，再从左到右给出第二行的N个整数……）给出矩阵中的N^2个整数，整数之间由空白字符分隔（空格或者空行）。 已知矩阵中整数的范围都在[-127, 127]。

输出描述：

输出最大子矩阵的大小。

输入：

4
0 -2 -7 0
9 2 -6 2
-4 1 -4  1
-1 8  0 -2

输出：

15

题目解析

二维前缀和矩阵的应用。

1. 初始化二维前缀和矩阵。
2. 枚举所有的子矩阵，求出最大子矩阵。

C++代码

#include <climits>
#include <iostream>
#include <vector>
using namespace std;

#define int long long

signed main()
{
    int n = 0;
    cin >> n;
    vector<vector<int>> vv(n, vector<int>(n));
    int res = INT_MIN;
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            cin >> vv[i][j];
            res = max(res, vv[i][j]);
        }
    }
    vector<vector<int>> preSum(n + 1, vector<int>(n + 1));
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
        {
            preSum[i][j] = preSum[i - 1][j] + preSum[i][j - 1] - preSum[i - 1][j - 1] + vv[i - 1][j - 1];
        }
    }
    // for(int i = 1; i <= n; ++i)
    // {
    //     for(int j = 1; j <= n; ++j)
    //     {
    //         cout << preSum[i][j] << " ";
    //     }
    //     cout << endl;
    // }
    for(int i = 1; i <= n; ++i) // 下次用x1,y1, x2,y2
    {
        for(int j = 1; j <= n; ++j)
        {
            for(int ii = 1; ii <= i; ++ii)
            {
                for(int jj = 1; jj <= j; ++jj)
                {
                    res = max(res, preSum[i][j] - preSum[i][jj - 1] - preSum[ii - 1][j] + preSum[ii - 1][jj - 1]); // 注意-1
                    // cout << i << j << " " << ii << jj << endl;
                }
            }
        }
    }
    cout << res << endl;
    return 0;
}

/*
0 -2 -7 0 
9  9 -4 -2 
-4 6 -2 -3 
-1 13 11 6 
9

0 -2 -9 -9 
9 9  -4 -2 
5 6 -11 -8 
4 13 -4 -3 
15

*/

Java代码

import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main
{
    public static int n;
    public static int[][] dp = new int[110][110];
    public static void main(String[] args) 
    {
        Scanner in = new Scanner(System.in);
        n = in.nextInt();
        for(int i = 1; i <= n; i++)
        {
            for(int j = 1; j <= n; j++)
            {
                int x = in.nextInt();
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + x;
            }
        }
        int ret = -127;
        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++)
                    {
                        ret = Math.max(ret, dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);
                    }
                }
            }
        }
        System.out.println(ret);
    }
}