Prefixmaxxing (Editorial)

Solution

Fact: if we make an operation on an index $i$, it's always optimal to choose x = \max(a_1,a_2,...,a_{i-1}).

Proof:

There are two cases:

If initially a_i \le \max(a_1,a_2,...,a_{i-1}), then choosing x = \max(a_1,a_2,...,a_{i-1}) increases the mog value by $1$.

Otherwise if a_i > \max(a_1,a_2,...,a_{i-1}), by choosing x = \max(a_1,a_2,...,a_{i-1}) the mog value for prefix $i$ stays the same but it could increase for the entire array by allowing new maximums after $i$.

Algorithm:

1. Traverse the array from left to right, keeping track of:

   • $mx1$: the current maximum seen so far.

   • $mx2$: the second largest value before the current maximum.

   • $c$: the current mog value (number of times a new maximum occurs up to this point).

   • $id$: the index of the latest maximum.

2. For each element $a[i]$:

   • If mx1 \le a_i, it is a new maximum:

     • Increment $c$ by $1$.

     • Update mx2 = mx1 and mx1 = a_i.

     • Update id = i.

   • Otherwise if mx2 \le a_i \le mx1, it can contribute to increasing later mog values if we change a_{id} (because the only thing preventing a_i from becoming a prefix maximum is a_{id}):

     • Increment dp_{id} by $1$.

     • Update mx2 = a_i.

3. After processing the array:

   • ans = c + \max(dp_i)

Complexity: $\mathcal{O}(n)$ per test case.

#include <bits/stdc++.h>
#define ll long long

using namespace std;

const ll N = 2e5+9;

ll n;
ll a[N],dp[N];

void solve()
{
    cin >> n;
    for(int i = 1 ; n>=i ; i++)
        cin >> a[i],dp[i]=0;
    ll mx1 = -2e9 , mx2 = -2e9 , c = 0 , id = 0;
    for(int i = 1 ; n>=i ; i++)
    {
        if(a[i]>=mx1)
        {
            c++;
            mx2=mx1;
            mx1=a[i];
            id=i;
        }
        else if(a[i]>=mx2)
        {
            mx2=a[i];
            dp[id]++;
        }
    }
    ll ans = c+1;
    if(ans==n+1)
        ans--;
    for(int i = 1 ; n>=i ; i++)
        ans=max(ans,c+dp[i]);
    cout << ans << "\n";
}

int main()
{
    ll T=1;
    cin >> T;
    while(T--)
        solve();
}