Editorial for DMOPC '14 Contest 5 P3 - Brotherly Sequence - Olympiads Online Judge

Editorial for DMOPC '14 Contest 5 P3 - Brotherly Sequence

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: Phoenix1369

Notice that only checking whether $| S[i] - S[i - 1] | \le 2$ $| S [i] - S [i - 1] | \leq 2$ and not $S[i + 1]$ $S [i + 1]$ is sufficient. Initialize an array $A$ $A$ of length $N$ $N$ with $1$ $1$ . For every element $i$ $i$ in the range $[1, N)$ $[1, N)$ that holds the brotherly sequence constraint, increase the length stored at $A[i - 1]$ $A [i - 1]$ by $1$ $1$ and assign it to $A[i]$ $A [i]$ . The maximum value in $A$ $A$ is the length of the longest brotherly subsequence.

Time Complexity: $\mathcal{O}(N)$ $O (N)$

Comments

There are no comments at the moment.