Prefixmaxxing (Розбір)

Розв’язок

Факт: якщо виконувати операцію в індексі $i$, оптимально обирати x = \max(a_1,a_2,...,a_{i-1}).

Доведення:

Є два випадки:

Якщо спочатку a_i \le \max(a_1,a_2,...,a_{i-1}), тоді вибір x = \max(a_1,a_2,...,a_{i-1}) збільшує mog на $1$.

Інакше, якщо a_i > \max(a_1,a_2,...,a_{i-1}), тоді вибір x = \max(a_1,a_2,...,a_{i-1}) не змінює mog для префікса $i$, але може збільшити його для всього масиву, дозволяючи нові максимуми після $i$.

Алгоритм:

1. Пройти масив зліва направо, зберігаючи:

   • $mx1$: поточний максимум.

   • $mx2$: друге за величиною значення перед максимумом.

   • $c$: поточне значення mog (кількість нових максимумів).

   • $id$: індекс останнього максимуму.

2. Для кожного $a[i]$:

   • Якщо mx1 \le a_i, це новий максимум:

     • Збільшити $c$ на $1$.

     • Оновити mx2 = mx1, mx1 = a_i.

     • Оновити id = i.

   • Інакше, якщо mx2 \le a_i \le mx1:

     • Збільшити dp_{id} на $1$.

     • Оновити mx2 = a_i.

3. Після обробки:

   • ans = c + \max(dp_i)

Складність: $\mathcal{O}(n)$ на тест.