Let $$$i_1, \ldots, i_k$$$ be the indices that maximize the value for each chosen subsequence in the optimal answer. Note that the answer itself is then equal to $$$a_{i_1} + \ldots + a_{i_k} + max(i_1, \ldots, i_k)$$$.

This means that if we fix $$$max(i_1, \ldots, i_k) = x$$$, we want to maximize the sum of the $$$k - 1$$$ elements of the array to the left of the $$$x$$$-th element. To do this, we can move left while maintaining a multiset that stores the current $$$k - 1$$$ maximum elements and keeping track of their sum. Then the answer will be the maximum over all $$$x$$$, $$$x + a_x + sum_x$$$, where $$$sum_x$$$ is the sum of the $$$k - 1$$$ maximum elements to the left of $$$x$$$.