Maximize sum of last three remaining elements [closed]

First of all, the order of deletion makes no difference. If we delete a_i and a_j, there is no difference in performing deletion on a_i or a_j first. (Theorem 1)

From Theorem 1, we can consider our deletion from the end of the array to begin.

For the Array[0..n-1], we consider element Array[n-1], there are two choices:

1. Delete array[n-1] by perform deletion on array[n-2]
2. Keep array[n-1] then goes to array[n-2]

So we define:

Sol(n, k) is the maximum answer by keeping k numbers in array[0..n]

Then we have:

Sol(n, k) = max(
  Sol(n - 1, k - 1) + array[n] # keep array[n]
  , Sol(n - 2, k) # delete both array[n] and array[n-1]
)

You can check my code for details:

ANS_MAX = 10**100


def sol(numbers):
    mem = {}

    def _sol(n, k):
        if mem.get((n, k)) is not None:
            return mem.get((n, k))
        if k == 0:
            return 0
        if n < 0:
            return -ANS_MAX
        ans = max(_sol(n - 2, k), _sol(n - 1, k - 1) + numbers[n])
        mem[(n, k)] = ans
        return ans

    return _sol(len(numbers) - 1, 3)


print(sol([1, 1, 1]))
print(sol([1, 1, 1, 1, 9, -9, 9]))