Верхняя граница через максимумы

В сумме соседних разностей каждое число получает коэффициент 2 в локальном максимуме, −2-2 в локальном минимуме и 0 в остальных местах. Максимумы и минимумы чередуются, их одинаковое количество k≤⌊N2⌋k\leq\left\lfloor \frac{N}{2}\right\rfloor. Поэтому сумма не больше удвоенной разности суммы kk наибольших и kk наименьших чисел, то есть 2k(N−k)2k(N-k). Это не больше 2⌊N2⌋⌈N2⌉2\left\lfloor \frac{N}{2}\right\rfloor \left\lceil \frac{N}{2}\right\rceil.

Учебный авторский материал. Порядок изучения не означает новую экспертную проверку решения или проверку источников.

Что нужно знать

Применение в задаче

Шаг 1. В сумме соседних разностей каждое число получает коэффициент 2 в локальном максимуме, −2-2 в локальном минимуме и 0 в остальных местах. Максимумы и минимумы чередуются, их одинаковое количество k≤⌊N2⌋k\leq\left\lfloor \frac{N}{2}\right\rfloor. Поэтому сумма не больше удвоенной разности суммы kk наибольших и kk наименьших чисел, то есть 2k(N−k)2k(N-k). Это не больше 2⌊N2⌋⌈N2⌉2\left\lfloor \frac{N}{2}\right\rfloor \left\lceil \frac{N}{2}\right\rceil.

Всё решение и условие задачи Решить задачу

Следующий шаг

Задачи по этому методу