Let f(k, s) be the answer to the problem if the plan is to steal k jewels with total weight s. We want to compute f(K, S).
Lemma: We have
f(2k, s) = \max_{|i| \le \lfloor n/2 \rfloor} f\Big(k, \lfloor s/2\rfloor-i\Big) + f\Big(k, \lceil s/2\rceil+i\Big)
and
f(2k+1, s) = \max_{1\le i\le n} a_i + f(2k, s-i).
Proof.
The second identity is easy.
Regarding the first identity, it is easy to see that the left-hand side is \ge than the right-hand side. Therefore we focus on showing the other inequality.
Let i_1, i_2, \dots, i_{2k} be a sequence of jewels such that \sum_{j=1}^{2k} i_j = s and \sum_{j=1}^{2k} a_{i_j} = f(2k, s).
Let J\subseteq \{1, 2, \dots, 2k\} be a subset of cardinality |J|=k such that \Big|\sum_{j\in J} i_j - s/2\Big| is minimal.
Without loss of generality, we may assume that \sum_{j\in J} i_j \le s/2.
Assume, by contradiction, that \sum_{j\in J} i_j < s/2 - n/2.
Thus, since \sum_{j\in J} i_j < \sum_{j\not\in J} i_j, there is j\in J and j'\not\in J so that i_j < i_{j'}. Let us consider J' := J\cup\{j'\}\setminus\{j\}.
Since 0\le i_{j'}-i_j < n, we have
\sum_{j\in J} i_j < \sum_{j\in J'} i_j \le \sum_{j\in J} i_j + n < \frac s2 + \frac n2 .
This latter chain of inequalities implies that \Big|\sum_{j\in J'} i_j - s/2\Big| < \Big|\sum_{j\in J} i_j - s/2\Big| which is a contradiction. Hence, we deduce
\frac s2 - \frac n2 \le \sum_{j\in J} i_j \le \frac s2 .
With s' := \sum_{j\in J} i_j, we have
f(2k, s) = \sum_{j=1}^{2k} a_{i_j} = \sum_{j\in J} a_{i_j} + \sum_{j\not\in J} a_{i_j} \le f(k, s') + f(k, s-s') \le \max_{0 \le i\le \lfloor n/2\rfloor} f\Big(k, \lfloor s/2\rfloor-i\Big) + f\Big(k, \lceil s/2\rceil+i\Big) .
Exploiting the lemma, one can solve the problem with dynamic programming. The states are the pairs (k, s), the transitions require O(n) time. It remains to bound the number of visited states.
In order to compute the answer for the states \{k\}\times[l, r],
- If k is odd, we have to visit \{k-1\}\times[l-n,r-1].
- If k is even, we have to visit \{k/2\}\times[ \lfloor l/2\rfloor -\lfloor n/2\rfloor, \lceil r/2 \rceil + \lfloor n/2\rfloor].
Let \{k\}\times [l, r] be the set of states visited for a given k; as a consequence of the observations above we have that r-l+1\le 3n if k is odd and r-l+1\le 4n is k is even. In any case, the number of states visited for a given k is O(n). Moreover, the number of k for which we visit at least one state is O(\log(K)).
Thus, the total number of states is O(n\log(K)).
Therefore, the complexity of this algorithm is O(n^2\log(K)).
The described algorithm can be implemented iteratively or recursively. The iterative implementation is much faster (due to cache-locality, simpler code, the use of vectors instead of hash-maps or deques). Depending on the implementation, the recursive version may get time limit exceeded.