每日打卡——AcWing126. 最大的和

2021-01-30

题意:

给定一个包含整数的二维矩阵,子矩形是位于整个阵列内的任何大小为 1 * 1 或更大的连续子阵列。

矩形的总和是该矩形中所有元素的总和。

在这个问题中,具有最大和的子矩形被称为最大子矩形。

例如,下列数组:

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

其最大子矩形为:

9 2 
-4 1 
-1 8

它拥有最大和 15。

思路

直接按照二维前缀和枚举左上坐标和右下坐标即可

代码

import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        int n,m;
        int [][]a=new int [105][105];
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        m=n;
        int [][]sum=new int [105][105];
        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                a[i][j]=sc.nextInt();
            }
        }

        for(int i=1;i<=n;i++) {
            for(int j=1;j<=m;j++) {
                sum[i][j]=sum[i][j-1]+sum[i-1][j]-sum[i-1][j-1]+a[i][j];
            }
        }


        int ans=-0x3f3f3f3f;
        for(int x1=1;x1<=n;x1++) {
            for(int y1=1;y1<=m;y1++) {
                for(int x2=x1;x2<=n;x2++) {
                    for(int y2=y1;y2<=m;y2++) {
                        int x=sum[x2][y2]-sum[x2][y1-1]-sum[x1-1][y2]+sum[x1-1][y1-1];
                        ans=Math.max(ans,x);
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

标题:每日打卡——AcWing126. 最大的和
作者:xiaob0
地址:https://xiaobo.net.cn/articles/2021/01/30/1612011248831.html