Let us say I have a finite dimension vector whose entries are purely positive numbers. I want to find the maximum sum of the entries subject to the constraint that if you choose a number in row $i$, you must not choose row $i+1$. In other words, you MUST skip at least one row. You can start from any other row.
For example: if $A = \begin{pmatrix} 1\\ 2\\ 3\\ 4 \end{pmatrix}$, then maximum sum for this matrix is $2 + 4 = 6$.
Another example: $B = \begin{pmatrix} 100\\ 1\\ 2\\ 100 \end{pmatrix}$ is $100+100 = 200$.
If there is no closed form way to solve this, I welcome an algorithmic approach.
Insights appreciated.
You can solve the problem via integer linear programming as follows. Let binary decision variable $x_i$ indicate whether entry $i$ is selected. The problem is to maximize $\sum_i A_i x_i$ subject to linear “conflict” constraints $x_i+x_{i+1}\le 1$.
You can also solve it via dynamic programming. For $k\in\{1,\dots,n+1\}$, let value function $f(k)$ denote the maximum sum obtained from the tail $(A_k,\dots,A_n)$. We want to compute $f(1)$. The boundary conditions are $f(n)=A_n$ and $f(n+1)=0$, and the DP recursion for $k\le n-1$ is $$f(k)=\max(A_k+f(k+2),f(k+1)).$$