Prefixmaxxing (Həll təhlili)

Həll

Fakt: əgər $i$ indeksində əməliyyat aparırıqsa, həmişə optimal seçim x = \max(a_1,a_2,...,a_{i-1}) olur.

Sübut:

İki hal var:

Əgər əvvəlcə a_i \le \max(a_1,a_2,...,a_{i-1}) olarsa, onda x = \max(a_1,a_2,...,a_{i-1}) seçmək mog dəyərini $1$ artırır.

Əks halda, əgər a_i > \max(a_1,a_2,...,a_{i-1}) olarsa, x = \max(a_1,a_2,...,a_{i-1}) seçilməsi prefix $i$ üçün mog dəyərini dəyişməz saxlayır, amma $i$-dən sonra yeni maksimumların yaranmasına imkan verərək bütün massiv üzrə mog dəyərini artıra bilər.

Alqoritm:

1. Massivi soldan sağa keçərək aşağıdakıları saxlayın:

   • $mx1$: indiyə qədərki maksimum.

   • $mx2$: cari maksimumdan əvvəlki ikinci ən böyük dəyər.

   • $c$: cari mog dəyəri (indiyə qədər yeni maksimumların sayı).

   • $id$: son maksimumun indeksi.

2. Hər $a[i]$ üçün:

   • Əgər mx1 \le a_i isə, bu yeni maksimumdur:

     • $c$-ni $1$ artırın.

     • mx2 = mx1, mx1 = a_i edin.

     • id = i edin.

   • Əks halda, əgər mx2 \le a_i \le mx1 isə:

     • dp_{id}-ni $1$ artırın.

     • mx2 = a_i edin.

3. Massiv işlənəndən sonra:

   • ans = c + \max(dp_i)

Mürəkkəblik: hər test üçün $\mathcal{O}(n)$.