To the Max

Time Limit:1000MS  Memory Limit:10000K
Total Submit:2053 Accepted:996

Description

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.

Input

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 100. The numbers in the array will be in the range [-127,127].

Output

Output the sum of the maximal sub-rectangle.

Sample Input 

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

 

Sample Output 

15

 

Source

Greater New York 2001

------------------------------------------------------------------------------------------------------

这是一道2维的求最大子段和的dp题，有几种解法：
1.开三维数组：
 1 #include <iostream>
 2 using namespace std;
 3 
 4 int n,i,j,k;
 5 int a[101][101],s[101][101][101];
 6 long b,sum,result;
 7 
 8 int main()
 9 {
10  while(cin>>n&&n!=EOF)
11  {
12      for(i=1;i<=n;i++)
13      for(j=1;j<=n;j++)
14     {
15        cin>>a[i][j];
16        s[i][i][j]=a[i][j];
17     }
18   for(i=1;i<n;i++)
19    for(j=i+1;j<=n;j++)
20     for(k=1;k<=n;k++)
21      s[i][j][k]=s[i][j-1][k]+a[j][k];//对于从第i到第j行的第k列的值
22   
23   result=0;
24   for(i=1;i<=n;i++)
25    for(j=1;j<=n;j++)
26    {
27     sum=0;
28     b=0;
29     for(k=1;k<=n;k++)//dp 就一维的
30     {
31      if(b>0)b+=s[i][j][k];
32      else b=s[i][j][k];
33      if(b>sum)sum=b;
34     }
35     if(sum>result)result=sum;
36    }
37   cout<<result<<endl;
38  }
39  return 0;
40 }
41 
42 
43 
2.用2维数组存放temp，求i行到j行的和，再求k列的最大子段和
#include <stdio.h>
#include <memory.h>
//该函数求一维数组的最大子段和
int getMax(int buf[100],int n)
{
    int temp[101],max=n*(-127);
    memset(temp,0,4*(n+1));
    int i;
    for(i=1;i<=n;i++)
    {
        temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i];
        if(max<temp[i])
            max=temp[i];
    }
    return max;
}

int main(void)
{
    int n,num[101][101],i,j,k,max,temp[101][101];
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&num[i][j]);
    max = -127*n*n;
    for(i=1;i<=n;i++)
    {
        memset(temp,0,sizeof(temp));
        for(j=i;j<=n;j++)
        {
            for(k=1;k<=n;k++)
            {
                temp[j][k] = temp[j-1][k]+num[j][k];
                
            }
            
            int this_max = getMax(temp[j],n);
            if(this_max>max)
                max = this_max;
        }
    }

    printf("%d\n",max);
    return 1;

}
3.压缩存储，用一维数组temp
#include <stdio.h>
#include <memory.h>
//该函数求一维数组的最大子段和
int getMax(int buf[100],int n)
{
    int temp[101],max=n*(-127);
    memset(temp,0,4*(n+1));
    int i;
    for(i=1;i<=n;i++)
    {
        temp[i] = (temp[i-1]>0?temp[i-1]:0)+buf[i];
        if(max<temp[i])
            max=temp[i];
    }
    return max;
}

int main(void)
{
    int n,num[101][101],i,j,k,max,temp[[101];
    scanf("%d",&n);
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            scanf("%d",&num[i][j]);
    max = -127*n*n;
    for(i=1;i<=n;i++)
    {
        memset(temp,0,sizeof(temp));
        for(j=i;j<=n;j++)
        {
            for(k=1;k<=n;k++)
            {
                temp[k] = temp[k]+num[j][k];
                
            }
            //二维转化为一维
            int this_max = getMax(temp,n);
            if(this_max>max)
                max = this_max;
        }
    }

    printf("%d\n",max);
    return 1;

}

嗯，比较经典的dp求最大子段和……