給定一個(gè)包含整數(shù)的二維矩陣，子矩形是位于整個(gè)陣列內(nèi)的任何大小為1 * 1或更大的連續(xù)子陣列。

矩形的總和是該矩形中所有元素的總和。
在這個(gè)問(wèn)題中，具有最大和的子矩形被稱(chēng)為最大子矩形。

例如，下列數(shù)組：
0 -2 -7 0
9 2 -6 2
-4 1 -4 1
-1 8 0 -2
其最大子矩形為：
9 2
-4 1
-1 8
它擁有最大和15。

輸入格式
輸入中將包含一個(gè)N*N的整數(shù)數(shù)組。
第一行只輸入一個(gè)整數(shù)N，表示方形二維數(shù)組的大小。
從第二行開(kāi)始，輸入由空格和換行符隔開(kāi)的N2個(gè)整數(shù)，它們即為二維數(shù)組中的N2個(gè)元素，輸入順序從二維數(shù)組的第一行開(kāi)始向下逐行輸入，同一行數(shù)據(jù)從左向右逐個(gè)輸入。
數(shù)組中的數(shù)字會(huì)保持在[-127,127]的范圍內(nèi)。

輸出格式
輸出一個(gè)整數(shù)，代表最大子矩形的總和。

數(shù)據(jù)范圍
1≤N≤100
輸入樣例：
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
輸出樣例：
15

代碼如下：

#include <iostream> using namespace std; const int N = 110; int a[N][N]; int main() {int n;cin>>n;for (int i = 1;i<=n;i++)for (int j = 1;j<=n;j++){int x;cin>>x;a[i][j] = a[i-1][j]+x;}int res = -1e8;for (int i = 1;i<=n;i++){for (int j = i;j<=n;j++){int f = 0;for (int k = 1;k<=n;k++){int cnt = a[j][k]-a[i-1][k];f = max(f,0)+cnt;res = max(res,f);}}}cout<<res<<endl;}

總結(jié)

以上是生活随笔為你收集整理的AcWing 126. 最大的和的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。