Hello Codeforces people, I have a question about problem 442C - Artem and Array . I looked at the solution in the tutorial, and I have no problem with it. Nevertheless, this is what I was trying before looking at the solution (let v[i], for i = 1, ..., n be the i-th element of the array):

• First, notice that we can choose the first and last element of the array right at the end (they will be our last choices)
• Second, we can choose the k-th element to be our penultimate choice (thus obtaining min(v[1], v[n]) points).

We can then solve the problem using dynamic programming: just let f(a, b) be the maximum number of points Artem gets when he plays with the (sub)array v[a..b].

This is a O(n³) solution, the answer to the problem is f(1, n). From here, was there something I could have noticed to get the running time down to O(n²) or ?

The only things I proved are that f(a, b + 1) ≥ f(a, b) and f(a - 1, b) ≥ f(a, b). If I'm not wrong, the official solution implies that the best k for f(a, b) is always the one for which v[k] is maximum.