algorithm - Maximum sum in a torus -

i trying solve following dynamic programming question on uva online judge:

a grid wraps both horizontally , vertically called torus. given torus each cell contains integer, determine sub-rectangle largest sum. sum of sub-rectangle sum of elements in rectangle. grid below shows torus maximum sub-rectangle has been shaded.

we know there exists similar , simpler problem: maximal sub-rectangle problem grid canot wrap. simpler variant, can first take cumulative of each row , apply kadane's algorithm in 2 for-loops solve problem. problem, impossible since grid can wrap around.

i have headstart on problem mirroring matrix 4 times simulate rotation of matrix. however, dynamic programming related problems, have formulate recurrence relation. not know how formulate recurrence problem. please advise me?

edit:

i tried using modified kadane's algorithm search largest rectangle of @ least size 1. however, still not getting right answer. reference, code listed below:

#include <cstdio> #include <algorithm> #include <list> using namespace std;  int main() {     int cc,r,c,r,c,inf = 9999;     scanf("%d",&cc);     while(cc--) {         scanf("%d",&r);         c = r;         r = c = 2 * r;         int l[r][c], sum[r+1][c];         fill_n(sum[0],c,0);          for(int = 0; < r; i++) {             for(int j = 0; j < c; j++) {                 scanf("%d",&l[i][j]);                 sum[i+1][j] = l[i][j];                 sum[i+1][c+j] = l[i][j];                 sum[r+i+1][j] = l[i][j];                 sum[r+i+1][c+j] = l[i][j];             }         }         for(int = 0; < c; i++) {             for(int j = 1; j < r+1; j++) {                 sum[j][i] += sum[j-1][i];             }         }         int g_max = -inf;         for(int = 0; < r; i++) {             for(int j = i+1; j < i+r+1; j++) {                 int t_max = sum[j][0]-sum[i][0], s = sum[j][0]-sum[i][0], l = 1, lo = 0, hi = 0;                 g_max = max(g_max,t_max);                 for(int k = l; k < c; k++) {                     s += (sum[j][k]-sum[i][k])-(sum[j][k-l]-sum[i][k-l]);                     t_max = max(t_max+(sum[j][k]-sum[i][k]),s);                     if(t_max > g_max) {                         g_max = t_max;                         lo = k - l - 1;                         hi = k;                         if(hi - lo == c-1) break;                     }                 }             }         }         printf("%d\n",g_max);     }     return 0; } 

given test case:

1 5 1 -1 0 0 -4 2 3 -2 -3 2 4 1 -1 5 0 3 -2 1 -3 2 -3 2 4 1 -4 

the grid in test case shown above. answer should 15. getting 24. not sure wrong algorithm since implemented kadane's algo stackoverflow answer. able me?