Skip to content

Instantly share code, notes, and snippets.

@whoshuu
Created November 16, 2017 19:42
Show Gist options
  • Save whoshuu/e8b4f87e1217098625b996a9938ec7d0 to your computer and use it in GitHub Desktop.
Save whoshuu/e8b4f87e1217098625b996a9938ec7d0 to your computer and use it in GitHub Desktop.
Folding Subsequence

Folding subsequence

This problem actually goes by another name, but to throw off cheaters, I'll use "folding" to describe the following property:

A folding sequence is a sequence of numbers where the difference between consecutive numbers in the sequence alternate in sign. A difference of 0 is defined to have no sign, so any sequence with consecutive repeating numbers is by definition a non-folding sequence.

To illustrate, these are folding sequences:

1
1, 2
1, 2, 1
1, 5, 3, 4, 2
6, 3, 5, 4, 5

and these are non-folding sequences:

1, 1
1, 2, 3
1, 5, 3, 4, 6

The problem is to write a program, taking a sequence of integers, that determines what the length of the longest folding subsequence is. For example, this sequence:

3, 6, 1, 2, 4, 3, 5, 5, 6, 1, 8, 3

has a maximum folding subsequence length of 9 (3, 6, 1, 4, 3, 6, 1, 8, 3 is an example folding subsequence).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment