title: Maximum sum in a torus
body: <p>I am trying to solve the following dynamic programming question on uva online judge:</p>
  
  <blockquote>
    <p>A grid that wraps both horizontally and vertically is called a torus.
    Given a torus where each cell contains an integer, determine the
    sub-rectangle with the largest sum. The sum of a sub-rectangle is the
    sum of all the elements in that rectangle. The grid below shows a
    torus where the maximum sub-rectangle has been shaded.</p>
  </blockquote>
  
  <p><a href="https://i.stack.imgur.com/IpDZc.jpg" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/IpDZc.jpg" alt="Image of a torus"></a></p>
  
  <p>We know that there exists a very similar and simpler problem: the maximal sub-rectangle problem where the grid canot wrap. For the simpler variant, we can first take the cumulative of each row and then apply kadane's algorithm in 2 for-loops to solve the problem. For this problem, this is impossible since the grid can now wrap around.</p>
  
  <p>I already have a headstart on this problem by mirroring the matrix 4 times to simulate the rotation of the matrix. However, with all dynamic programming related problems, we have to formulate the recurrence relation. I do not know how to formulate the recurrence for this problem. Could anyone please advise me?</p>
  
  <p>Edit:</p>
  
  <p>I tried using modified kadane's algorithm to search the largest rectangle of at least size 1. However, I am still not getting the right answer. For reference, my code is listed below: </p>
  
  <pre><code>#include &lt;cstdio&gt;
  #include &lt;algorithm&gt;
  #include &lt;list&gt;
  using namespace std;
  
  int main() {
      int cc,r,c,R,C,INF = 9999;
      scanf("%d",&amp;cc);
      while(cc--) {
          scanf("%d",&amp;r);
          c = r;
          R = C = 2 * r;
          int l[r][c], sum[R+1][C];
          fill_n(sum[0],C,0);
  
          for(int i = 0; i &lt; r; i++) {
              for(int j = 0; j &lt; c; j++) {
                  scanf("%d",&amp;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 i = 0; i &lt; C; i++) {
              for(int j = 1; j &lt; R+1; j++) {
                  sum[j][i] += sum[j-1][i];
              }
          }
          int g_max = -INF;
          for(int i = 0; i &lt; r; i++) {
              for(int j = i+1; j &lt; 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 &lt; 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 &gt; 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;
  }
  </code></pre>
  
  <p>Given this test case:</p>
  
  <pre><code>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
  </code></pre>
  
  <p>The grid in the test case is as shown above. The answer should be 15. But I am getting 24. I am not sure what is wrong with my algorithm since I implemented the kadane's algo from another stackoverflow answer. Is anyone able to help me?</p>