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 and not S[i + 1] is sufficient. Initialize an array A of length N with 1. For every element i in the range [1, N) that holds the brotherly sequence constraint, increase the length stored at A[i - 1] by 1 and assign it to A[i]. The maximum value in A is the length of the longest brotherly subsequence.

Time Complexity: \mathcal{O}(N)


Comments

There are no comments at the moment.