What will the algorithm look like?

Question

Algorithms

The task is given: A man and a robot are playing a game. The first move is made by a man. There are N cards with numbers on the table (numbers are written on the cards). The robot and the person take the cards in turn. When the person’s turn comes, he has 2 options: take 1 card or skip the move. Once in the whole game, a person can take two cards at once in 1 move. The robot does not have such opportunities, he takes each once only one card and cannot skip moves. Find a winning trajectory for a person, i.e. such a set of moves in which all the cards taken by a person would give a larger amount than the cards taken by the robot.
Input:
1 2 -6 7 4 3
Output (cards with numbers): (First, the person skips a move, the robot takes: 1; then the person takes: 2; the robot takes -6;
a person takes 2 cards: 7.4; the robot takes: 3)
2,7,4
Help with the algorithm for this problem.
Here is my algorithm, but I don't think it's correct:
1) We consider simple cases:
A) when there is 1 card, then the person takes it.
B) when there are 2 cards, if both cards are not negative, then the person takes both, if at least 1 is negative, then he takes the maximum of them
2) The usual case (for N> 2):
linearly compare consecutive cards with each other, but then question: it may be that there are several pairs of consecutive cards whose sums are equal. How to proceed in this case and find the optimal trajectory?
I will be glad if you help me to solve this problem.

Answer 1

Solution through dynamic programming. F(k) - the best amount that can be collected from cards, starting from k, when you can take 2 cards once, g(k) is the same, but you can no longer take 2 cards.
g(k) = max(a[k]+g(k+2),g(k+1));- or you take the first card, then the robot takes the next one and then the task is repeated. The second option - you skip this card, then the robot takes it. The task is repeated from the next card.

f(k) = max(a[k]+a[k+1]+g(k+3), a[k] + f(k+2), f(k+1));

- in the same way, we either take 2 cards, or 1, or 0. If we take 2, then in the future we can no longer take 2, we will have to take g (k + 3).
Here is a C++ solution (instead of 2 functions, a flag is used, is it possible to take 2 cards)

vector<int> dp[2]; // заполнен MIN_INT, размером с n.
vector<int> take[2]; // размером с n.
int f(const vector<int> &a, int k, int can_take_two) {
   if(k >= n) return 0;
   if (dp[k][can_take_two] > MIN_INT) return dp[k][can_take_two];
   // skip;
   int best = f(a, k+1, can_take_two);
   take[k][can_take_two] = 0;
   // take 1;
   int cur = f(a, k+2, can_take_two) + a[k];
   if (cur > best) {
     best = cur;
     take[k][can_take_two] = 1;
   }
   if (can_take_two && k + 1 < n) {
      cur = f(k+3, 0) + a[k] + a[k+1];
      if (cur > best) {
        best = cur;
        take[k][can_take_two] = 2;
      }
   }
   dp[k][can_take_two] = best;
   return best;
}
//...
// f(a, 0, 1) - вернет лучшую сумму.

//Для восстановления ответа можно воспользоваться массивом take, который хранит для каждого состояния, сколько карточек брать:

k = 0; ct = 1;
while (k <n) {
  num = take[k][ct];
  for (j = 0; j < num; ++j) {
    cout << a[k+j] << " ";
  }
  if (num == 2) ct = 0;
  k += num + 1;
}

If you only need the sum, and not the set of numbers itself, then you can expand the recursion into 2 nested loops (one from n to 0, the other from 0 to 1) and store only the last 3 rows of the dp array.

Answer 2

Here is the solution. Not sure if you can figure it out - but try

l = [1, 2, -6, 7, 4, 3]
le = len(l)
step0, step1, step2 = [None, []], [None, None], [None, None]
l += [0, 0]  # добьём незначащими нулями
for i in range(le):
    x, y, z = l[i:i + 3]
    for j, pos in enumerate(step0):
        if pos is None:
            continue
        newpos = [*pos, -x]
        if step1[j] is None or sum(step1[j]) < sum(newpos):
            step1[j] = newpos
        newpos = [*pos, x, -y]
        if step2[j] is None or sum(step2[j]) < sum(newpos):
            step2[j] = newpos
    step0, step1, step2 = step1, step2, [[*pos, x, y, -z], None]
best = max((pos for step in (step0, step1, step2) for pos in step if pos is not None), key=sum)
print(best[:le])