title: Efficient C/C++ algorithm on 2-dimensional max-sum window
body: <p>I have a <code>c[N][M]</code> matrix where I apply a max-sum operation over a <code>(K+1)²</code> window. I am trying to reduce the complexity of the naive algorithm.</p>
  
  <p>In particular, here's my code snippet in C++:</p>
  
  <pre><code>&lt;!-- language: cpp --&gt;
  
  int N,M,K;
  std::cin &gt;&gt; N &gt;&gt; M &gt;&gt; K;
  
  std::pair&lt; unsigned , unsigned &gt; opt[N][M];
  unsigned c[N][M];
  
  // Read values for c[i][j]
  // Initialize all opt[i][j] at (0,0).
  
  for ( int i = 0; i &lt; N; i ++ ) {
    for ( int j = 0; j &lt; M ; j ++ ) {
  
      unsigned max = 0;
      int posX = i, posY = j;
  
      for ( int ii = i; (ii &gt;= i - K) &amp;&amp; (ii &gt;= 0); ii -- ) {
        for ( int jj  = j; (jj &gt;= j - K) &amp;&amp; (jj &gt;= 0); jj -- ) {
  
          // Ignore the (i,j) position
          if (( ii == i ) &amp;&amp; ( jj == j )) {
            continue;
          }
  
          if ( opt[ii][jj].second &gt; max ) {
  
            max = opt[ii][jj].second;
            posX = ii;
            posY = jj;
  
          }
        }
      }
  
      opt[i][j].first  = opt[posX][posY].second;
      opt[i][j].second = c[i][j] + opt[posX][posY].first;
  
    }
  }
  </code></pre>
  
  <p>The goal of the algorithm is to compute <code>opt[N-1][M-1]</code>.</p>
  
  <p>Example: for <code>N = 4, M = 4, K = 2</code> and:</p>
  
  <pre><code>c[N][M] = 4 1 1 2
            6 1 1 1
            1 2 5 8
            1 1 8 0
  </code></pre>
  
  <p>... the result should be <code>opt[N-1][M-1] = {14, 11}</code>.</p>
  
  <p>The running complexity of this snippet is however <strong>O</strong>(N M K²). My goal is to <strong>reduce</strong> the running time complexity. I have already seen posts like <strong><a href="https://stackoverflow.com/questions/10732841/sliding-window-minimum-maximum-in-2d">this</a></strong>, but it appears that my "filter" is not separable, probably because of the sum operation.</p>
  
  <hr>
  
  <p>More information (<strong>optional</strong>): this is essentially an algorithm which develops the optimal strategy in a "game" where:</p>
  
  <ul>
  <li>Two players lead a single team in a <code>N × M</code> dungeon.</li>
  <li>Each position of the dungeon has <code>c[i][j]</code> gold coins.</li>
  <li>Starting position: <code>(N-1,M-1)</code> where <code>c[N-1][M-1] = 0</code>.</li>
  <li>The active player chooses the next position to move the team to, from position <code>(x,y)</code>.</li>
  <li>The next position can be any of <code>(x-i, y-j), i &lt;= K, j &lt;= K, i+j &gt; 0</code>. In other words, they can move only left and/or up, up to a step <code>K</code> per direction.</li>
  <li>The player who just moved the team gets the coins in the new position.</li>
  <li>The active player alternates each turn.</li>
  <li>The game ends when the team reaches <code>(0,0)</code>.</li>
  <li>Optimal strategy for both players: maximize their own sum of gold coins, if they know that the opponent is following the same strategy.</li>
  </ul>
  
  <p>Thus, <code>opt[i][j].first</code> represents the coins of the player who will now move from <code>(i,j)</code> to another position. <code>opt[i][j].second</code> represents the coins of the opponent.</p>