Algorithm for Choosing Numbers with the Maximum/Minimum Sum from a Sequence

Question

These are two related questions that I found as part of an informatics competition; i.e. a competition in which the aim is to write a computer program that outputs what is asked.

Q1. Given a finite sequence of numbers (the input), we move across it left to right and at each step, we can either choose the current number or exclude it. However, we cannot exclude three numbers in a row. Find the minimum possible sum of such a selection.

Q2. Given a finite sequence of numbers (the input), we move across it left to right and at each step, we can either choose the current number or exclude it. However, we cannot choose three numbers in a row. Find the maximum possible sum of such a selection.

Of course, we can always brute-force this by looking at all possible selections and summing them, but I found a better way of solving the first question. We start by choosing the minimum among the first three elements, and then choose the minimum of the next three from the current position. But if we choose, say, the second element, and then we choose the first element after that (in the next step), we combine those two into a single step, omitting the second element.

My first question is: does this approach give the correct answer? And my second question is: is there a similar better way of solving the second question?

Answer 1

I can only answer your first question after fiddling around with this problem a little in C#. What I found is, that your approach fails to give the minimum possible sum, when the length of the sequence is particularly short ( between 10 and 200 integers ). One algorithm that some times beats yours for short sequences is to just pick every third item.

You can find the code that i've used to test this here Although most of the time it will give the best result, in about 1/3 of the test cases it failed to do so.

So my guess for your second question is that there is a better way to solve this, although i can't tell you the algorithm for it. What I'm thinking is that you will have to optimize the picks in a way, such that for the last picked number the amount of remaining numbers in the sequence is 2 or 1.

Answer 2

The short answer to both questions: Use dynamic programming!

Consider the following algorithm to answer $Q1$ where we assume the input is stored in an array $a$ of length $n$: (note that I use c++ like syntax and assume that $n \geq 2$)

int dp[n + 1];
dp[0] = 0;
dp[1] = a[0];
dp[2] = min(dp[0], dp[1]) + a[1];
for(int i = 3; i < n + 1; i++){
   dp[i] = min(dp[i - 3], dp[i - 2], dp[i - 1]) + a[i - 1];
}
int result = min(dp[n], dp[n - 1], dp[n - 2]);

The meaning of the $i$-th entry of the $dp$ table is the following:

$dp[i] = k \iff$ $k$ is the minimum sum reachable under your constraints for the first $i$ numbers of the input given that we cannot exclude element $i$

For example for the first $0$ elements of the input we know that the answer must be $0$. Hence $dp[0] = 0$. For the first $1$ elements of the input we know that the answer must be $0$. But under the additional constraint that we must include the first element for the $dp$ entry we get that $dp[1] = a[0]$. For the first $2$ elements of the input we know that the answer must be $0$. But under the condition that we must include the first element for the $dp$ entry we get that $dp[2] = a[1]$ (Note that in the code I overcomplicated this for the sake of seeing the pattern). For the first $3$ elements of the input we know that the answer must be the minimum of $a[0], a[1], a[2]$. But given that the third element must be included we get $dp[3] = a[2]$. And so on...

In order to answer $Q2$ you can use a very similar approach: Use a $dp$-table and try to answer the following question: If you knew what the solution is for the first $i$ entries for all $i < k$, how can you find the solution for the first $k$ entries?