欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

AcWing寒假每日一题——Day22

程序员文章站 2022-07-12 21:36:54
...

126.最大的和

一、问题描述

给定一个包含整数的二维矩阵,子矩形是位于整个阵列内的任何大小为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。
输入格式
输入中将包含一个N*N的整数数组。第一行只输入一个整数N,表示方形二维数组的大小。从第二行开始,输入由空格和换行符隔开的N2个整数,它们即为二维数组中的N2个元素,输入顺序从二维数组的第一行开始向下逐行输入,同一行数据从左向右逐个输入。
数组中的数字会保持在[-127,127]的范围内。
输出格式
输出一个整数,代表最大子矩形的总和。
数据范围
1≤ N N N≤100
输入样例:

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

输出样例:

15

二、问题分析

左上角和右下角两个点可以确定一个矩形。枚举这两个点要用4个for循环肯定会超时,这里我们枚举边界。将每个点处理为它上面这列的前缀和,枚举上下边,将矩阵看为“1行”,找出最大的矩形。
代码如下(示例):

#include<iostream>
#include<algorithm>
using namespace std;
int n,q[110][110],res=-1e9;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            cin>>q[i][j];
            q[i][j]+=q[i-1][j];
        }
    for(int i=1;i<=n;i++)
        for(int j=i;j<=n;j++)
        {
            int last =0;
            for(int k=1;k<=n;k++)
            {
                last=max(last,0)-q[i-1][k]+q[j][k];
                res=max(res,last);
            }
        }
        cout<<res<<endl;
        return 0;
}