3
$\begingroup$

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} &-1 &4 &-6 &-1 &-2 &-5 &10 \\ &5 &-7 &2 &1 &-9 &-13 &2 \\ &2 &4 &-10 &3 &1 &2 &6 \\ &3 &2 &7 &1 &-7 &4 &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.

Improve this question
$\endgroup$
3
  • 2
    $\begingroup$ Nice exercise! However, we discourage posts that simply state a problem out of context, and expect the community to solve it. What have you tried? Where did you get stuck? We do not want to just do your exercise for you; we want you to gain understanding. However, as it is we do not know what your underlying problem is, so we can not begin to help. Assuming you tried to solve it yourself and got stuck, it may be helpful if you edited the question to write your thoughts and what you could not figure out. Which algorithm design paradigms have you tried? What did you try for each one? $\endgroup$ – D.W.♦ Jan 18 '16 at 17:16
  • 2
    $\begingroup$ Also, in what context did you encounter this problem? What's the motivation? Please give attribution to the source of this exercise (e.g., the textbook or instructor who invented it) -- this is a nice exercise, and I'd like to be able to share it with others and give credit where credit is due. $\endgroup$ – D.W.♦ Jan 18 '16 at 17:17
  • $\begingroup$ An IP-formulation should be approachable, but does not yield an efficient algorithm per se. $\endgroup$ – Raphael♦ Jan 19 '16 at 13:24
1
$\begingroup$

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)$.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.