**PROBLEM LINK:**

link:Contest

Author: @kostya_by

Tester: @white_king

**DIFFICULTY:**

Easy

**PROBLEM:**

This can be solved using dynamic programming.

Call best_forward[i] to be the maximum prosperity of a sequence that ends at i. This can be computed as:

best_forward[i]=max(A[i], best_forward[i-1] + A[i]).

From this, you may easily compute the maximum prosperity of any sequence that ends anywhere between 0…i as:

cumulative_best_forward[i] = max(cumulative_best_forward[i-1], best_forward[i]).

Similarly let best_backward[i] be the maximum prosperity of a sequence starting at i

best_backward[i]=max((ll)A[i], best_backward[i+1] + A[i]). Similarly, you compute cumulative_best_backward[i].

The answer is simply

max_{j=K+2 to N} (cumulative_best_forward[j-K-1] + cumulative_best_backward[j]).