LEQMAX - Editorial

editorial
,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

TBD

PREREQUISITES:

None

PROBLEM:

Given an array A, find its longest good subsequence.
A subsequence B is called good if it satisfies B_1 = 1 and B_i \le \max(B_1, \ldots, B_{i-1}) + 1.

EXPLANATION:

A simple greedy algorithm solves this task: iterate over the array A from left to right, and simply include the next element in the subsequence if possible.

That is, for each i = 1, 2, \ldots, N,

  • If A_i is at most 1 plus the largest element chosen so far, include A_i into the subsequence.
    Otherwise, it cannot be included.
    If A_i is included, update the maximum element with A_i.

The answer is then the number of chosen elements.

For convenience, assume that initially the largest chosen element is 0 (so that the constraint of the first chosen element being 1 gets satisfied automatically, and doesn’t need to be special-cased.)

It’s fairly easy to prove that this greedy is optimal: the first chosen element must be 1 so we might as well choose the leftmost occurrence of 1 (if we don’t choose it, it can always be inserted into the start of the subsequence to increase its length by 1), then the second chosen element must be either 1 or 2 so we might as well choose the leftmost remaining occurrence of one of them, and so on.
The greedy algorithm accomplishes exactly this.

TIME COMPLEXITY:

\mathcal{O}(N) per testcase.

CODE:

Editorialist's code (PyPy3) 
for _ in range(int(input())):
    n = int(input())
    a = list(map(int, input().split()))
    
    ans = 0
    mx = 0
    for x in a:
        if x <= mx+1:
            ans += 1
            mx = max(mx, x)
    print(ans)
2

(post deleted by author)