Find a maximum sum in matrix, subject to special constraint I have a matrix of size $N \cdot M$ filled with integer values $A[i][j]$. I want to choose some numbers so that their sum is maximal. But there is one very important constraint. If I choose numbers in the $i$-th row from interval $[a, b]$, then I have to also take the interval $[\max(1, a - 1), \min(b + 1, M)]$ in the $i + 1$-th row.  In other words, if I use all of $A[i][a], \dots, A[i][b]$, then I also have to use the elements $A[i+1][\max (1, a-1)],\dots ,A[i+1][\min (b+1, M)]$.

I can't think of any algorithm for this.  I don't even have any idea how to brute-force it. Could someone please help me solve that? I think the optimal solution should have $O(N \cdot M)$ complexity or something like that.

Example input: $N=4$, $M=7$, and
$$A = 
\left(\begin{matrix}
&amp;-1 &amp;4 &amp;-6 &amp;-1 &amp;-2 &amp;-5 &amp;10 \\
&amp;5 &amp;-7 &amp;2 &amp;1 &amp;-9 &amp;-13 &amp;2 \\
&amp;2 &amp;4 &amp;-10 &amp;3 &amp;1 &amp;2 &amp;6 \\
&amp;3 &amp;2 &amp;7 &amp;1 &amp;-7 &amp;4 &amp;5
\end{matrix}\right).
$$  

For this problem instance, the maximal sum is $40$. This can be achieved by taking the 5 in the first column, the 3 in the fourth column, the 1 in the fifth column and the 2 in the last column as the summits of the triangles.
This can be solved in $O(NM)$ time using dynamic programming.

Given any solution, let $s$ denote the smallest index $s$ such that $a[s][1]$ is selected.  (It follows that $a[1][1],\dots,a[s-1][1]$ are not selected and that $a[s][1],\dots,a[N][1]$ are selected.)  This partitions solutions based on the value of $s$, i.e., based on which entries from the first column are selected in that solution.  There are only $N$ possible values for $s$.

Now define $f(s,t)$ to be the largest sum that is possible by selecting some entries from the submatrix $a[1..N][t..M]$, subject to the restriction that you choose all of $a[s..N][t]$ and don't choose any of $a[1..s-1][t]$.  You can easily find a recurrence relation that expresses $f(s,t)$ in terms of a few values of the form $f(s',t+1)$.  This immediately yields a simple dynamic programming algorithm with running time $O(NM)$.