We are given an array $a_1, a_2, ..., a_n$ where $-10^9\leq a_i\leq 10^9$ and $2\leq n\leq 3000$ and we want to compute the value of the maximum subsequence of this array such that the subsequence has gaps of non-increasing sizes between the positions of consecutive subsequence elements in the array. We call this condition $C$ for short.
The first thing that jumps to mind is to use dynamic programming. We can define $\text{dp}[i, l]$ to be the maximum subsequence ending at $a_i$ which satisfies $C$ where the previous subsequence element is at $i-l$.
Our base case is
$$\forall 1\leq l<n : \text{dp}[1, l] = a_1$$
then our transition function is
$$\text{dp}[i, l] = \max_{l\leq l' \text{ and } i-l-l' \geq 1}\{\text{dp}[i-l, l']\} + a_i$$
since if we arrive at $a_i$ with the last jump having length $l$, we know that we must have arrived from $a_{i-l}$ where we arrived to that with $l'\geq l$. In the above transition equation, we assume that $i>l$ otherwise $\text{dp}[i, l] = -\text{INF}$ since the jump of length $l$ would longer than possible.
However, a straightforward implementation yields an $O(n^3)$ solution which is too slow. We are looking for $O(n^2)$ or better. Although in the contest I did not find anything better.
No comments:
Post a Comment