Maximum Sum#12782

Maximum Sum (Editorial)

Problem author:

Maryan Shyika

Prepared by:

Maryan Shyika

Tutorial:

Maryan Shyika

Idea

Notice that for a fixed index $i$ such that $s_{i} = 0$ s_i=0, it is enough to know only one index $j > i$ j>i such that $s_{j} = 1$ s_j=1 and the value $a_{j}$ a_j is as large as possible.

Indeed, once $i$ is fixed, the value $a_{i}$ a_i does not change, so in order to maximize

a_{i} + a_{j}

a_i+a_j

we should always choose the maximum possible $a_{j}$ a_j among all positions to the right for which $s_{j} = 1$ s_j=1.

Therefore, we iterate through the array from right to left and maintain

m x = max a_{j}

mx=\max a_j

over all already processed positions $j$ such that $s_{j} = 1$ s_j=1.

If at the current position $i$ we have $s_{i} = 0$ s_i=0, then, provided that $m x > a_{i}$ mx>a_i, we can update the answer with

a_{i} + m x .

a_i+mx.

If $s_{i} = 1$ s_i=1, we update

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

mx=\max(mx,a_i).

Thus, every position is processed exactly once.

The overall time complexity is — $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}) .