經典動態規劃： 尋找最大矩形 POJ1050

1050:To the Max

總時間限制: 5000ms 內存限制: 65536kB

描述

Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1*1 or greater located within the whole array. The sum of a rectangle is the sum of all the elements in that rectangle. In this problem the sub-rectangle with the largest sum is referred to as the maximal sub-rectangle.

As an example, the maximal sub-rectangle of the array:

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2

is in the lower left corner:

9 2

-4 1

-1 8

and has a sum of 15.

輸入

The input consists of an N * N array of integers. The input begins with a single positive integer N on a line by itself, indicating the size of the square two-dimensional array. This is followed by N^2 integers separated by whitespace (spaces and newlines). These are the N^2 integers of the array, presented in row-major order. That is, all numbers in the first row, left to right, then all numbers in the second row, left to right, etc. N may be as large as 500. The numbers in the array will be in the range [-127,127].

輸出

Output the sum of the maximal sub-rectangle.

樣例輸入

4

0 -2 -7 0 9 2 -6 2

-4 1 -4 1 -1

8 0 -2

樣例輸出

15

來源

Greater New York 2001

原題鏈接：OpenJudge - 1050:To the Max

一、題意分析

題意翻譯過來就是，給你N^2個數字，構成一個矩陣，需要你從其中找出和最大的子矩陣。例如：

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2

這個矩陣中最大的子矩陣就是：

9 2

-4 1

-1 8

其和為15，程序輸出15就可以了。

二、思路分析

咋一看，就有一種使用暴力枚舉法的衝動，但先別急，每當有這個想法時，必先冷靜分析一下：時間夠用？

注意到：

N may be as large as 500.

一個500*500的矩陣，其中的子矩陣數量是驚人的，時間雖然給了5000ms，但肯定不夠。

每當想用暴力的演算法解決問題，但時間又不夠的時候，咱們就可以開始考慮動態規划了。

這個問題可以分解成一個稍簡單的問題：

給你你一行數量為n的數組row[n]，如何從中找出和最大的一段子數組？

我們可以這樣考慮：

用一個大小同樣為n的數組maxrow存儲以每個以row[i]結尾的最大子序列的和。

舉個例子：

如果：

row[5]={1,2,3,-7,5}

那麼：

maxrow[0]=1

maxrow[1]=1+2=3

maxrow[2]=1+2+3=6

maxrow[3]=1+2+3-7=-1

maxrow[4]=5

可以發現：

maxrow[i]=maxrow[i-1]>0?maxrow[i-1]+row[i]:row[i];

maxrow中最大的那個元素就是我們要找的最大子序列的和。

回到原來的問題我們就會發現，它也可以化歸成同樣的問題：

一個數組即可看做行為1的矩陣，而矩陣通過行與行中每個元素的相加可以壓縮成一個數組。

N*N的矩陣可以組成1+2+3+……N個不同的數組，而最大的子矩陣之和就藏在其中某個數組的maxrow當中。

三、AC code

內存:2048kB 時間:231ms

#include <iostream>using namespace std;int board[501][501]{};int maxrow[501]{};int maxmatrix=0;int main(int argc, const char * argv[]) { int n; cin>>n; for(int i=0;i<n;i++)//input { for(int j=0;j<n;j++) { cin>>board[i][j]; } } int temprow[n]; for(int i=0;i<n;i++)//i for rows { for(int c=0;c<n;c++)//initialize { temprow[c]=0; } for(int j=i;j<n;j++)//j for rows { for(int c=0;c<n;c++)// c for cols { temprow[c]+=board[j][c]; } for(int c=0;c<n;c++) { if(c==0) { maxrow[c]=temprow[c]; }else{ maxrow[c]=maxrow[c-1]>0?maxrow[c-1]+temprow[c]:temprow[c]; } maxmatrix=max(maxmatrix,maxrow[c]); } } } cout<<maxmatrix<<endl;}

廣告時間啦~

理工狗不想被人文素養拖後腿？不妨關注微信公眾號：

為你讀最好的書~

推薦閱讀：