URAL 1146 Maximum Sum & HDU 1081 To The Max (DP)

 1 #include <iostream>
 2 #include <stdio.h>
 3 #include <string.h>
 4 
 5 using namespace std;
 6 
 7 int sum[110][110] ;
 8 int main()
 9 {
10     int n ,m;
11     while(~scanf("%d",&n))
12     {
13         memset(sum,0,sizeof(sum)) ;
14         for(int i = 1 ; i <= n ; i++)
15         {
16             for(int j = 1 ; j <= n ; j++)
17             {
18                 scanf("%d",&m) ;
19                 sum[i][j] = sum[i-1][j]+m ;
20             }
21         }
22         int ans = -9999999 ;
23         for(int i = 1 ; i <= n ; i++ )
24             for(int j = i ; j <= n ; j++)
25             {
26                 int cnt = 0 ;
27                 for(int k = 1 ; k <= n ; k ++)
28                 {
29                     cnt += sum[j][k]-sum[i-1][k] ;
30                     ans = max(cnt,ans) ;
31                     if(cnt < 0) cnt = 0 ;
32                 }
33             }
34         printf("%d",ans) ;
35     }
36     return 0;
37 }