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?
Best Answer
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.