Okay here's my reattempt at solving this

Define $$$deletable[l][r]$$$ as whether or not you can fully delete the subarray $$$l...r$$$. The idea is that nested deletions always occur in disjoint subarrays, so a full solution might be "delete a subarray of $$$5k$$$, then $$$3k$$$, then $$$k$$$, then $$$2k$$$". If you had a series of deletions that overlapped, they actually form one big subarray.

Then:

• If the sum is not a multiple of $$$k$$$, then the answer is always no.
• If the sum is $$$k$$$, then the answer is yes.
• If the sum is $$$2k$$$, then the answer is yes if and only if there is a deletable subarray inside us with sum $$$k$$$.
• If the sum is $$$xk$$$, then the answer is yes if and only if there is a deletable subarray inside us with sum $$$(x-1)k$$$.

To calculate this, first in $$$O(n^2)$$$ you can use prefix sums to load every array that is deletable with sum $$$k$$$.

Then to find arrays that are deletable with sum $$$2k$$$, you can:

• For each $$$r$$$, store the tightest subarray $$$l_r...r$$$.
• Then to check if there are any contained within subarray $$$a...b$$$, you RMQ over $$$r = a...b$$$ and see if the highest value you get is $$$\ge a$$$.
• The RMQ is $$$O(1)$$$ amortized if you sweep.

Time: $$$O(n^3)$$$: $$$n$$$ levels of sums, $$$n^2$$$ subarrays to check each time. Not too ugly and I think correct.

Once you have all of this then you can do a DP through the original array to see the max sum that you can recover.

$$$dp[i]$$$ is the number of deletions you can get, starting at $$$i$$$ and ending at the end.

$$$dp[i]$$$ transitions from $$$(j-i) + dp[j]$$$ if you can delete subarray $$$i...j-1$$$, and $$$dp[i+1]$$$ if you don't delete anything.

This time complexity is just $$$O(n^2)$$$.

BTW: Are negative/zero numbers allowed? If they aren't I'm wondering if the $$$O(n^3)$$$ step can be sped up a bit because there can now only be $$$n$$$ subarrays at each level $$$k, 2k, ...$$$ (because a superarray would always have strictly higher sum).