ZOJ 1074 To the Max(DP 最大子矩阵和)
Problem
Given a two-dimensional array of positive and negative integers, a sub-rectangle is any contiguous sub-array of size 1 x 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 x 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 100. The numbers in the array will be in the range [-127,127].
Output
Output the sum of the maximal sub-rectangle.
Input
4
0 -2 -7 0 9 2 -6 2
-4 1 -4 1 -1
8 0 -2
Output
15
代码如下:
1 # include<stdio.h> 2 # include<string.h> 3 # define N 101 4 int main(){ 5 int a[N][N],b[N]; 6 int n,i,j,k; 7 while(scanf("%d",&n)!=EOF) 8 { 9 for(i=0;i<n;i++) 10 for(j=0;j<n;j++) 11 scanf("%d",&a[i][j]); 12 int max= -12345; 13 for(i=0;i<n;i++) //第i行到第j行的最大子矩阵和 14 { 15 memset(b,0,sizeof(b)); 16 for(j=i;j<n;j++) 17 { 18 int sum=0; 19 for(k=0;k<n;k++) 20 { 21 b[k] += a[j][k]; 22 sum += b[k]; 23 if(sum<0) sum=b[k]; 24 if(sum>max) max=sum; 25 } 26 } 27 } 28 printf("%d\n",max); 29 } 30 return 0; 31 }
相关文章
- 解决Cannot change version of project facet Dynamic web module to 2.5
- org.springframework.web.multipart.MultipartException: Failed to parse multipart servlet request; nested exception is java.io.IOException: The temporary upload location [/tmp/tomcat.1428942566812653608
- Reporting Service 服务启动时报错The service did not respond to the start or control request in a timely fashion
- [Git] How to rename your remote branch
- The nodes should be added to the underlying vendor clusterware before adding them to the CRS cluster
- [CSS 3] Use the Border-Radius CSS Property to Define Horizontal and Vertical Radius
- [FAQ] PHP Warning: json_encode(): double INF does not conform to the JSON spec
- try to navigate from button to line item page
- How to handle the generic error Cannot read property md of undefined
- why metadata request for GM4 via http will be redirected to https via 307 s
- association in CDS view is converted to LEFT OUTER MANY TO ONE JOIN in the runtime
- how to find element's document section
- git push报错 fatal: The current branch master has no upstream branch. To push the current
- The current user does not have write permissions to the target environment.
- EnvironmentNotWritableError: The current user does not have write permissions to the targe...
- 【问题解决】The connection to the server localhost:8080 was refused
- 【问题解决】Got permission denied while trying to connect to the Docker daemon socket at 。。。
- Ubuntu下交叉编译make menuconfig时出错:Unable to find the ncurses libraries or the required header files.
- Error:The supplied javaHome seems to be invalid. I cannot find the java executable. Tried location:
- 解决运行js代码报错—Warning: To load an ES module, set “type“: “module“ in the package.json or use the .mjs
- git push报错 fatal: The current branch master has no upstream branch. To push the current
- (六)Jenkins部署项目报错The username you provided is not allowed to use the text-based Tomcat Manager (error