Максимальна сума#12782

Максимальна сума (Розбір)

Автор задачі:

Мар'ян Шийка

Підготував:

Мар'ян Шийка

Розбір:

Мар'ян Шийка

Ідея

Помітимо, що для фіксованого індексу $i$ , для якого $s_{i} = 0$ s_i=0, нам достатньо знати лише один індекс $j > i$ j>i, для якого $s_{j} = 1$ s_j=1 та значення $a_{j}$ a_j є максимально можливим.

Справді, якщо ми вже зафіксували $i$ , то значення $a_{i}$ a_i не змінюється, тому для максимізації суми

a_{i} + a_{j}

a_i+a_j

нам завжди вигідно взяти найбільше можливе $a_{j}$ a_j серед усіх позицій праворуч, де $s_{j} = 1$ s_j=1.

Тому пройдемо масив справа наліво та будемо підтримувати значення

m x = max a_{j}

mx=\max a_j

серед усіх уже розглянутих позицій $j$ , для яких $s_{j} = 1$ s_j=1.

Якщо на поточній позиції $i$ маємо $s_{i} = 0$ s_i=0, то, якщо $m x > a_{i}$ mx>a_i, можемо оновити відповідь значенням

a_{i} + m x .

a_i+mx.

Якщо ж $s_{i} = 1$ s_i=1, оновимо

m x = max (m x, a_{i}) .

mx=\max(mx,a_i).

Таким чином, кожну позицію ми обробляємо рівно один раз.

Загальна асимптотика — $O (n)$ .

s_{i} = 0

j > i

s_{j} = 1

a_{j}

a_{i}

a_{i} + a_{j}

a_{j}

s_{j} = 1

m x = max a_{j}

s_{j} = 1

s_{i} = 0

m x > a_{i}

a_{i} + m x .

s_{i} = 1

m x = max (m x, a_{i}) .