DMOPC '14 Contest 5 P3 - Brotherly Sequence

View as PDF

Submit solution


Points: 5 (partial)
Time limit: 2.0s
Memory limit: 64M

Author:
Problem type

Kamina is interested in brotherly sequences. A brotherly sequence is a sequence B where for every index i between [2, N], |B[i-1]-B[i]| \le 2. Given a sequence of numbers S of length N (3 \le N \le 100), what is the length of the longest contiguous brotherly subsequence it contains?

Input Specification

The first line of input will contain the integer N.
The second line of input will contain N space-separated integers making up the sequence S. The numbers in S are in the range [-1000, +1000].

Output Specification

The positive integer length of the longest contiguous brotherly subsequence in the sequence S.

Sample Input

5
1 1 2 4 8

Sample Output

4

Note

A subsequence of a sequence is a sequence that is formed by deleting some elements of the original sequence, but preserving the relative order of the remaining elements. A contiguous subsequence is a subsequence formed by deleting some prefix and some suffix of the sequence (possibly empty for either or both).


Comments


  • 0
    20220680  commented on Dec. 1, 2022, 4:24 p.m.

    if you fail on batch 12, try these two sample cases:

    5

    30 20 1 2 3

    3

    3 3 3

    The answer should be 3 for both of them.


  • 0
    jlsajfj  commented on Feb. 16, 2016, 2:35 a.m.

    Shouldnt it be contest 5?


    • 0
      r3mark  commented on Feb. 16, 2016, 2:46 a.m.

      No, because Exam Time was the fourth contest of the 2014 DMOPCs. The URL for the Exam Time problems had "ce" instead of "c4" though, so I guess that's why the URL for all the 2014 DMOPCs after Exam Time were 1 off.


  • 1
    Axiomschema  commented on March 10, 2015, 9:37 p.m.

    Can we have another input/output sample?


    • -9
      FatalEagle  commented on March 10, 2015, 10:15 p.m.

      This comment is hidden due to too much negative feedback. Show it anyway.


  • 0
    Spirit  commented on March 10, 2015, 9:03 p.m.

    Can there be an explanation for the sample output? Such as what the longest contiguous brotherly subsequence would be?


    • 0
      Xyene  commented on March 10, 2015, 9:09 p.m.

      For the sample input, we can remove the last element of the sequence. The resulting subsequence is maximal.