Максимум суммы

[Andrey173]

Решение понятно, спасибо всем. Но вот, что написал mserg не совсем понял, Вы можете как-то более формально описать?)

[ewert]

Да он всё вполне формально описал, разве что не везде вполне аккуратно.

Пункт 1-й: если все члены ненулевые, то можно увеличить ту сумму произведений, сделав один из членов нулевым, перекинув его значение на соседнее (через один). Это -- наименее тривиальный момент; ну уж с этим сами разберитесь.

Остальное -- уже достаточно очевидно.

Пункт второй: если есть хотя бы один ноль, то все нули можно сосредоточить на сплошном участке (поскольку перемещение какого-либо нуля, не находившегося на этом участке, на тот самый участок -- ту сумму произведений как минимум не уменьшит).

Пункт третий. После того, как у нас есть два сплошных участка: состоящий из нулей и из ненулей -- мы можем потихонечку откусывать по одному элементу ненулевого участка с любого его конца, сокращая при этом его длину и заведомо не уменьшая при этом сумму произведений.

Вот так в конце концов и придём к всего лишь трём подряд идущим ненулевым членам.

Правда, насчёт единственности полученной максимальной конфигурации -- придётся ещё чуток попыхтеть; но не очень сильно.