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] | \le 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)$ ~\mathcal{O}(N)~

Comments

There are no comments at the moment.