poj1050

 1 /* 
 2  * File:   main.cpp
 3  * Author: liaoyu <liaoyu@whu.edu.cn>
 4  *
 5  * Created on April 1, 2014, 5:34 PM
 6  */
 7 
 8 #include <iostream>
 9 #include <stdio.h>
10 #include <stdlib.h>
11 #include <string.h>
12 #include <cmath>
13 #include <algorithm>
14 using namespace std;
15 
16 int a[105][105];
17 
18 int maxSubArray(int n, int* a)
19 {
20     int max = 0x80000000;
21     int b = a[0];
22     for (int i = 1; i < n; i++) {
23         if (b > 0)b += a[i];
24         else b = a[i];
25         if (b > max)max = b;
26     }
27     return max;
28 }
29 int b[105];
30 
31 int main()
32 {
33     int n;
34     scanf("%d", &n);
35     int max = 0x80000000;
36     for (int i = 0; i < n; i++)
37         for (int j = 0; j < n; j++)
38             scanf("%d", &a[i][j]);
39     for (int i = 0; i < n; i++)
40         for (int j = i; j < n; j++) {
41             for (int l = 0; l < n; l++) {
42                 b[l] = 0;
43                 for (int k = i; k <= j; k++) {
44                     b[l] += a[l][k];
45                 }
46             }
47             int tmp = maxSubArray(n, b);
48             if (tmp > max)max = tmp;
49         }
50     printf("%d\n", max);
51 }