ural 1146. Maximum Sum

时间：2024-08-07 20:34:38

1146. Maximum Sum

Time limit: 0.5 second
Memory limit: 64 MB
Given a 2-dimensional array of positive and negative integers, find the sub-rectangle with the largest sum. 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. A sub-rectangle is any contiguous sub-array of size 1 × 1 or greater located within the whole array.
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-hand corner and has the sum of 15.

Input

The input consists of an N × N array of integers. The input begins with a single positive integerN on a line by itself indicating the size of the square two dimensional array. This is followed byN 2 integers separated by white-space (newlines and spaces). These N 2 integers make up the array in row-major order (i.e., all numbers on the first row, left-to-right, then all numbers on 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

The output is the sum of the maximal sub-rectangle.

Sample

input output 
4

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2

15
Difficulty: 97
题意：求最大的子矩阵
分析：很经典的题。
知道最大子段和的做法。
然后枚举矩阵的上下界，按照最大子段和的做法做。
 /**

 Create By yzx - stupidboy

 */

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <cmath>

 #include <deque>

 #include <vector>

 #include <queue>

 #include <iostream>

 #include <algorithm>

 #include <map>

 #include <set>

 #include <ctime>

 #include <iomanip>

 using namespace std;

 typedef long long LL;

 typedef double DB;

 #define MIT (2147483647)

 #define INF (1000000001)

 #define MLL (1000000000000000001LL)

 #define sz(x) ((int) (x).size())

 #define clr(x, y) memset(x, y, sizeof(x))

 #define puf push_front

 #define pub push_back

 #define pof pop_front

 #define pob pop_back

 #define ft first

 #define sd second

 #define mk make_pair

 inline int Getint()

 {

     int Ret = ;

     char Ch = ' ';

     bool Flag = ;

     while(!(Ch >= '' && Ch <= ''))

     {

         if(Ch == '-') Flag ^= ;

         Ch = getchar();

     }

     while(Ch >= '' && Ch <= '')

     {

         Ret = Ret *  + Ch - '';

         Ch = getchar();

     }

     return Flag ? -Ret : Ret;

 }

 const int N = ;

 int n, arr[N][N];

 int sum[N][N], p[N];

 inline void Input()

 {

     scanf("%d", &n);

     for(int i = ; i <= n; i++)

         for(int j = ; j <= n; j++) scanf("%d", &arr[i][j]);

 }

 inline int Work(int *arr)

 {

     int ret = arr[], cnt = arr[];

     for(int i = ; i <= n; i++)

     {

         if(cnt < ) cnt = arr[i];

         else cnt += arr[i];

         ret = max(ret, cnt);

     }

     return ret;

 }

 inline void Solve()

 {

     int ans = -INF;

     for(int i = ; i <= n; i++)

         for(int j = ; j <= n; j++)

             sum[i][j] = sum[i - ][j] + arr[i][j];

     for(int i = ; i <= n; i++)

         for(int j = i; j <= n; j++)

         {

             for(int k = ; k <= n; k++)

                 p[k] = sum[j][k] - sum[i - ][k];

             int cnt = Work(p);

             /*if(ans < cnt)

             {

                 ans = cnt;

                 printf("%d %d %d\n", ans, i, j);

             }*/

             ans = max(ans, cnt);

         }

     cout << ans << endl;

 }

 int main()

 {

     freopen("a.in", "r", stdin);

     Input();

     Solve();

     return ;

 }

相关文章