Preparing the statement, recent submissions, and submit form.
Consider
The answer is . Thus, using prefix sums and checking every interval solves the problem in time.
Intuition
Suppose from the beginning that some optimal solution has the following form.
If the positive part is the interval , then the condition determines
Proof
Fix any feasible . For a nonnegative real number , keep exactly the indices satisfying . The remaining indices form a disjoint union of contiguous intervals.
Solution written by GPT5.6
The objective value is then .
Therefore, among solutions of this form, the best interval is one maximizing , and it achieves . It remains only to prove that no more complicated choice of can exceed .
For one such interval , there are adjacent pairs whose two indices both remain. By the definition of , .
Summing over all remaining intervals, at height the number of adjacent pairs whose two indices remain is at most .
Let be the number of adjacent pairs whose two indices remain at height . Each pair is counted exactly while , so the objective value is . Therefore, integrating the inequality above over all gives
Now choose an interval attaining . For every , set
and set all other to . This satisfies the constraint, and the objective value is .
Therefore, is exactly the maximum value.
