The longest alternating sequence in C++

The first line of the input stream contains integer n. The second line contains n (1 <= n <= 1000) integers { a[1], a[2], a[3], ... , a[n] }, abs(a[i]) < 10^9.

Find the longest alternating subsequence { a[i1], a[i2].. , a[ik] } of the sequence a that is the subsequence such that i1 < i2 < ... < ik, every two adjacent elements are different, and every three adjacent elements a[i' - 1], a[i'], a[i' + 1] meet one of the following conditions: (a[i' - 1] < a[i'] && a[i'] > a[i' + 1]) || (a[i' - 1] > a[i'] && a[i'] < a[i' + 1]) where k is maximized.

The output stream should contain the subsequence { a[i1], a[i2].. , a[ik] }.

Important condition. If there are several subsequences that satisfy this condition you need to choose the subsequence with the minimum i1. From all subsequences with the same i1 you need to choose the one with minimum i2. And so on.

For example:

1) n = 13, a = { 8, 7, 4, 3, 2, 5, 6, 9, 8, 7, 3, 2, 4}.

Output is { 8, 7, 9, 3, 4}.

2) n = 10, a = { 1, 4, 2, 3, 5, 8, 6, 7, 9, 10}.

Output is { 1, 4, 2, 8, 6, 7}.

A short explanation of my algorithm on example:

8, 7, 4, 3, 2, 5, 6, 9, 8, 7, 3, 2, 4

---|----1----|--|---2--|-|---3-----|-|4|

In this case there are 4 subsequence: 2 decreasing (1, 3) and 2 increasing (2, 4). So the maximum number of elements in the longest alternating subsequence will be 5 (number of subcequencws + 1, because of the first element, which is always included in the begining of longest alternating subsequence). Now we need to find the optimal elements, that satisfy important condition.

At every iterarion of the main cycle I have to subsequence: increasing and decreasing (seq[0] and seq[1], one of them is current), which I change with every iteration.

For example,

1) seq[1] = {7, 4, 3, 2} and seq[0] = {5, 6, 9} , seq[1] is current;

2) seq[0] = {5, 6, 9} is current, seq[1] = {8, 7, 3, 2};

3) seq[1] = {8, 7, 3, 2} is current, seq[0] = 4.

In each iteration I choose an element in current subsequence according to these rules:

1) if the current subsequence is decreasing, than choose the leftmost element in seq[1][i] ( i >=currentLimiter ), which is less than some element in increasing subsequence seq[0][j], and remember the current position currentLimiter=j of seq[0][j];

For the case of seq[1] = {7, 4, 3, 2} and seq[0] = {5, 6, 9}, where seq[1] is current, element 7 is selected, as 7 < 9, and the currentLimiter = 2 (index of 9).

2) if the current subsequence is increasing, than choose the leftmost element in seq[0][i] ( i >=currentLimiter ), which is greater than some element in decreasing subsequence seq[1][j], and remember the current position currentLimiter=j of seq[1][j];

For the case of seq[0] = {5, 6, 9}, seq[1] = {8, 7, 3, 2}, where seq[0] is current, element 9 is selected, as we can search only from index 2 (currentLimiter = 2) and 9 > 8, and the currentLimiter = 0 (index of 8).

There is my solution for this problem:

std::vector<long long> findLongestAlternantSequence(std::vector<long long> &inputArray)
{
if (inputArray.size() == 1 || inputArray.size() == 2)
return inputArray;

std::vector<int> arrayOfDifferences;

for (size_t i = 0; i < inputArray.size() - 1; ++i)
{
//if the next element greater than current, add 1 to arrayOfDifferences
//else add 0. So we have array of markers, that shows whether
//the sequence encreases or decreases
arrayOfDifferences.push_back((inputArray[i] - inputArray[i + 1] > 0) ? 1 : 0);
}

std::vector<long long> longestAlternantSequence;
//seq - vector of 2 subsequences (increasing and decreasing)
//seq[0] will be filled with increasing subsequence
//seq[1] will be filled with decreasing subsequence

std::vector< std::vector<long long> > seq;
std::vector<long long> v1;
std::vector<long long> v2;
seq.push_back(v1);
seq.push_back(v2);

int currentVal = arrayOfDifferences[0];
// pointer to the current element of input sequence
size_t pos = 0;
// pointer to the element of increasing/decreasing subsequence
// from which I can search for the next element
size_t currLimiter = 0;
// the first element is always result sequence
longestAlternantSequence.push_back(inputArray[0]);

while (pos < arrayOfDifferences.size())
{
seq[currentVal].clear();

//fill current subsequence seq[currentVal] with new elements
//of increasing or decreasing subsequence
// currentVal can be 0 or 1; 0 indicates that the current subsequence
// is increasing, 1- decresing
while (pos < arrayOfDifferences.size()  && currentVal == arrayOfDifferences[pos])
{
seq[currentVal].push_back(inputArray[pos + 1]);
++pos;
}

currentVal = (currentVal + 1) % 2;

if (currentVal == 1)
{
if (seq[1].size() != 0)
{
int k = 0;
int s = currLimiter;
while ( s < seq[1].size() && seq[1][s] >= seq[0][k])
{
++k;
if ( k == seq[0].size())
{
k = 0;
++s;
}
}
if (s < seq[1].size())
{
longestAlternantSequence.push_back(seq[1][s]);
}
currLimiter = k;
}
}

else
{
if (seq[0].size() != 0)
{
int k = 0;
int s = currLimiter;
while (s < seq[0].size() && seq[0][s] <= seq[1][k])
{
++k;
if ( k == seq[1].size())
{
k = 0;
++s;
}
}
if (s < seq[0].size())
{
longestAlternantSequence.push_back(seq[0][s]);
}
currLimiter = k;
}
}
}
// push the element of the last subsequence
longestAlternantSequence.push_back(seq[(currentVal + 1) % 2][currLimiter]);

return longestAlternantSequence;
}


I've spent a lot of time on this problem, but still not convinced that I solved it correctly. I will be grateful if you specify my mistakes and find the tests for which my program is wrong.

There are two bugs related to consecutive equal entries:

• According to the problem specification, the result needs to be strictly alternating — ai and ai+1 may not be equal to each other. For the input { 8, 8, 8 }, the output should be { 8 }. Your algorithm produces { 8, 8 }.
• A two-element input is not a trivial base case. For the input { 5, 5 }, you cannot immediately return the input as the output.

I'll make the trivial observation that the inputArray parameter should be const. Just call it input; the "Array" adds nothing of value, and in any case, it's a std::vector, not an array.

Wherever you say (n + 1) % 2 to map 0 to 1 and vice versa, you can just say !n.

That said, I can make absolutely no sense of how your code works. It appears to work correctly for all sequences I tried, except for the bugs mentioned above. If you could describe its theory of operation, I think I would like to give it a proper review.

I've written an implementation that makes sense to me. I'll admit that it does not perform nearly as efficiently as yours.

std::vector<T> altSubsequence(const std::vector<T> &input) {
if (input.size() <= 1)
return input;

const size_t DESCENDING = 0, ASCENDING = 1;
std::vector<size_t> subsequenceLength[] = {
std::vector<size_t>(input.size(), 1),
std::vector<size_t>(input.size(), 1)
};
std::vector<size_t> nextElement[] = {
std::vector<size_t>(input.size(), 0),
std::vector<size_t>(input.size(), 0)
};
size_t maxSubsequenceLength[] = { 1, 1 };

for (int i = input.size() - 1; i >= 0; --i) {
for (size_t dir = DESCENDING; dir <= ASCENDING; dir++) {
for (size_t j = i + 1; j < input.size(); j++) {
if ((dir == DESCENDING) ? (input[i] > input[j])
: (input[i] < input[j])) {
if (subsequenceLength[dir][i] <= subsequenceLength[!dir][j]) {
subsequenceLength[dir][i] = 1 + subsequenceLength[!dir][j];
nextElement[dir][i] = j;

if (subsequenceLength[dir][i] > maxSubsequenceLength[dir]) {
maxSubsequenceLength[dir] = subsequenceLength[dir][i];
}
if (subsequenceLength[dir][i] == 1 + maxSubsequenceLength[!dir]) {
break;
}
}
}
}
}
}

std::vector<T> result;
// Which direction to start?
size_t dir = (subsequenceLength[DESCENDING][0] > subsequenceLength[ASCENDING][0]) ? DESCENDING :
(subsequenceLength[ASCENDING][0] > subsequenceLength[DESCENDING][0]) ? ASCENDING :
(nextElement[DESCENDING][0] < nextElement[ASCENDING][0]) ? DESCENDING : ASCENDING;
size_t i = 0;
do {
result.push_back(input[i]);
i = nextElement[dir][i];
dir = !dir;
} while (i != 0);
return result;
}


Explanation

This solution is based on dynamic programming. We want to know, that is the longest descending-first alternating subsequence if the input only consisted of elements inputi, inputi + 1, …, inputn, and what is the longest ascending-first subsequence, that starts with inputi? We start with i = n, where obviously the maximum subsequence length is 1. Then we consider i = n - 1 to see how it might be incorporated into an existing optimal sequence, etc., until i = 0, at which point we will know what the optimal sequence looks like.

Example:

input = { 8, 7, 4, 3, 2, 5, 6, 9, 8, 7, 3, 2, 4 }

1. Considering just the last element { 4 }, the longest alternating descending-first subsequence has length 1, and the longest ascending-first subsequence also has length 1.
2. Considering { 2, 4 }, the longest descending-first subsequence is { 2 }, which has length 1. The longest ascending-first subsequence is { 2, 4 }, which has length 2.
3. Considering { 3, 2, 4 }, the longest descending-first subsequence is { 3, 2, 4 } — it can connect to the 2-element ascending-first we found in step 2. The longest ascending-first subsequence anchored by 3 is { 3, 4 } — it connects to the descending-first subsequence found in step 1.
4. Considering { 7, 3, 2, 4 }, the longest descending-first subsequence is { 7, 3, 4 } — it connects to the 2-element ascending-first we found in step 3. (How do we know? Of the subsequent elements smaller than 7, we find the one that is the start of the longest ascending-first sequence that is known to exist.) The longest ascending-first subsequence is { 7 } — there is no element larger than 7.
5. Considering { 8, 7, 3, 2, 4 }, the longest descending-first subsequence is { 8, 3, 4 } — it connects to the 3-element ascending-first we found in step 3. (How do we know? Of the subsequent elements smaller than 3, we find the one that is the start of the longest ascending-first sequence that is known to exist, favouring { 8, 3, 4 } over { 8, 2, 4 } because 3 is an earlier entry.) The longest ascending-first subsequence is { 8 } — there is no element larger than 8.
6. Considering { 9, 8, 7, 3, 2, 4 }, the longest descending-first subsequence is { 9, 3, 4 } — it connects to the 2-element ascending-first we found in step 3. The longest ascending-first subsequence is { 9 } — there is no element larger than 9.
7. Considering { 6, 9, 8, 7, 3, 2, 4 }, the longest descending-first subsequence that starts with 6 is { 6, 3, 4 } — it connects to the 2-element ascending-first we found in step 3. (We walk consider elements 3, 2, and 4, which are all smaller than 6. Of those, 3 is the one that starts the longest known ascending-first sequence.) The longest ascending-first subsequence is { 6, 9, 3, 4 } — connecting to the 3-element descending-first subsequence found in step 6.
8. Considering { 5, 6, 9, 8, 7, 3, 2, 4 }, the longest descending-first subsequence that starts with 5 is { 5, 3, 4 } — it connects to the 2-element ascending-first we found in step 3. The longest ascending-first subsequence is { 5, 9, 3, 4 } — connecting to the 3-element descending-first subsequence found in step 6.
9. Considering { 2, 5, 6, 9, 8, 7, 3, 2, 4 }, the longest descending-first sequence is { 2 }. The longest ascending-first sequence is { 2, 9, 3, 4 }.
10. Considering { 3, 2, 5, 6, 9, 8, 7, 3, 2, 4 }, the longest descending-first sequence is { 3, 2, 9, 3, 4 }. The longest ascending-first sequence is { 3, 5, 3, 4 } — connecting to the descending-first sequence found in step 8.
11. Considering { 4, 3, 2, 5, 6, 9, 8, 7, 3, 2, 4 }, the best descending-first sequence is { 4, 3, 2, 9, 3, 4 }. The best ascending-first sequence is { 4, 6, 3, 4 } — connecting to the descending-first sequence found in step 7.
12. Considering { 7, 4, 3, 2, 5, 6, 9, 8, 7, 3, 2, 4 }, the best descending-first sequence is { 7, 4, 6, 3, 4 }. The best ascending-first sequence is { 7, 9, 3, 4 } (using step 6).
13. Considering all input { 8, 7, 4, 3, 2, 5, 6, 9, 8, 7, 3, 2, 4 }, the best descending-first sequence is { 8, 7, 9, 3, 4 } (using step 12). The best ascending-first sequence is { 8, 9, 3, 4 } (using step 6).
14. The descending-first sequence is longer, so it wins.

Why do we work backwards from the end? Because the problem, as stated, favours earlier elements. The first element of the input will always be included in the result. Therefore, when we finally reach the first element, we have our answer.

In the code, the two subsequenceLength vectors store the length of the longest descending-first and ascending-first anchored at element i. The nextElement vectors contain the indexes that tell us how those chains are constructed. Each of the two maxSubsequenceLength just contains the maximum value of subsequenceLength, as a shortcut to prevent the algorithm from being fully O(n2).

• Thank you for finding these bugs! I've added some explanations to my algorithm. It is not easy to follow I suppose. So ask questions if something is not clear. – Ann Orlova Oct 1 '13 at 8:17

You have essentially implemented a greedy algorithm. Each time you detect a change in the trend, you add an element to the result. It's just that your code for finding which element to add is hard to follow because the cryptic variable names lack meaning. Also, I think it is useful to introduce a class representing a monotonic run, just like you described in your explanation.

Your greedy strategy seems to work, although I can't prove that it's correct.

Here's my implementation of what you described, with fixes for the bugs I noted in my other answer. I think you'll find it more expressive than your original.

#include <assert.h>
#include <vector>

//////////////////////////////////////////////////////////////////////

/**
* This class represents a monotonically non-increasing (trendtype = DN)
* or monotonically non-decreasing (trendtype = UP) run of elements in
* a vector.
*/
template<typename T>
class MonotonicRun {
public:
typedef enum trendtype { DN = 0, UP = 1 } trendtype;

/**
* begin and end should point to either:
* - the front of the vector,
* - just past the back of the vector,
* - a local extremum
*/
MonotonicRun(const std::vector<T> &vector,
typename std::vector<T>::const_iterator begin,
typename std::vector<T>::const_iterator end) :
// C++11 constructor delegation
MonotonicRun(vector, begin, end, trendForInitialRun(vector, begin, end)) {
}

MonotonicRun(const std::vector<T> &vector,
typename std::vector<T>::const_iterator begin,
typename std::vector<T>::const_iterator end,
trendtype trend) :
vector(&vector),
b(begin),
e(end),
t(trend) {
}

inline typename std::vector<T>::const_iterator begin() const {
return b;
}

inline void begin(typename std::vector<T>::const_iterator b) {
this->b = b;
}

inline typename std::vector<T>::const_iterator end() const {
return e;
}

inline trendtype trend() const {
return t;
}

inline bool hasNext() const {
return begin() != vector->end();
}

MonotonicRun<T> next() const {
assert(hasNext());
typename std::vector<T>::const_iterator it;
T e;
switch (trend()) {
case DN:
for (it = end(), e = *it; it != vector->end() && *it >= e; ++it) {
e = *it;
}
return MonotonicRun(*vector, end(), it, UP);
case UP:
for (it = end(), e = *it; it != vector->end() && *it <= e; ++it) {
e = *it;
}
return MonotonicRun(*vector, end(), it, DN);
}
}

private:
static trendtype trendForInitialRun(const std::vector<T> &vector,
typename std::vector<T>::const_iterator begin,
typename std::vector<T>::const_iterator end) {
assert(begin == vector.begin());
if (end == vector.end()) {
// This is the initial and only run.  Construct a degenerate
// run; its trendtype won't matter since it only serves to
// signal the end of iteration.
return DN;
} else if (*begin < *end) {
return DN;
} else if (*begin > *end) {
return UP;
}
// If *end == *begin, then then we failed to locate all consecutive
// repeating elements when constructing this run.
assert(false);
}

const typename std::vector<T> *vector;
typename std::vector<T>::const_iterator b, e;
trendtype t;
};

//////////////////////////////////////////////////////////////////////

template<typename T>
std::vector<T> longestAlternatingSubsequence(const std::vector<T> &input) {
if (input.size() <= 1) {
return input;
}
std::vector<T> result;

// Construct an initial run consisting of the first element.  If any
// immediately following elements are equal to it, include those too.
typename std::vector<T>::const_iterator it;
for (it = input.begin(); it != input.end() && *it == input.front(); ++it);
MonotonicRun<T> thisRun(input, input.begin(), it);

do {
MonotonicRun<T> nextRun = thisRun.next();

// Find the earliest element of this run that will let us accommodate
// the next run.
typename std::vector<T>::const_iterator thisIt, nextIt;
for (thisIt = thisRun.begin(); thisIt != thisRun.end(); ++thisIt) {
for (nextIt = nextRun.begin(); nextIt != nextRun.end(); ++nextIt) {
if ( ((thisRun.trend() == thisRun.DN) && (*thisIt < *nextIt)) ||
((thisRun.trend() == thisRun.UP) && (*thisIt > *nextIt)) ) {
nextRun.begin(nextIt);
goto PUSH_RESULT;
}
}
}
assert(!nextRun.hasNext());
thisIt = thisRun.begin();

PUSH_RESULT: result.push_back(*thisIt);
thisRun = nextRun;
} while (thisRun.hasNext());

return result;
}


I would also observe that the code should be templatized, becaused there is no reason to be limited to long long only. Any type would work, as long as it supports the comparison operators.

Your approach is not very idiomatic. It is very hard to read, and reason-about. Spotting mistakes is not easy. I will not even attempt it, as I think some major rewriting should be your first priority. I think your current approach of trying to solve the entire problem in one big function is a big part of the reason why you had to work so long on it! Of course, algorithms are hard, but you can use well-known building blocks to build larger ones.

I would try to mimic the Standard Library / Boost as much as possible. This means using divide-and-conquer to split your problem up into manageable pieces, each of which are easy to reason about without knowing too much of the rest of the problem.

• top-level function should be a function template taking bidirectional iterators arguments instead of a container, and returning a pair of iterators instead of a container. This makes the algorithm usable with other data types and avoids unnecessary copying.

i.e. like this:

template<class BidirIt>
std::pair<BidirIt, BidirIt>
find_longest_alternating_subsequence(BidirIt first, BidirIt last)

• because you are iterating 3 elements in lock-step, I would use a boost::zip_iterator from the Boost.Iterator library. This will tie the adjacent elements into a boost::tuple from the Boost.Tuple library. I would let your top-level function delegate to a find_longest_alternating_subsequence_helper that takes such zip_iterators.

i.e. define the starting iterators of the helper function like this:

auto first_triple_it = boost::make_zip_iterator(
boost::make_tuple(first, std::next(first), std::next(first, 2))
);

auto last_triple_it = boost::make_zip_iterator(
boost::make_tuple(std::prev(last, 2), std::prev(last), last)
);

• use a function object predicate is_alternating_triple that takes a zip_iterator to formally define the alternating condition that you are looking for

i.e. like

struct is_alternating_triple
{
template<class TripleIt>
bool operator()(TripleIt it) const
{
auto const& e0 = it.get<0>();
auto const& e1 = it.get<1>();
auto const& e2 = it.get<2>();

return (
((e0 < e1) && (e1 > e2)) ||
((e0 > e1) && (e1 < e2))
)
}
};

• Let's look back what these suggestions would achieve: you can repeatedly use a simple one-dimensional search over triples to find elements satisfying a predicate, and compute whether the length of the last sequence was larger than the maximum so far. This suggests using std::find_if and std::find_if_not from the Standard Library in order to find the beginning and end of each alternating sequence.

i.e. a main loop inside find_longest_alternating_subsequence_helper like this

// init max sequence found so far
for (auto it = first_triple_it; it != last_triple_it; /* NO ++it here, see loop*/) {
auto seq_beg = std::find_if(it, last_triple_it, is_alternating_triple);
if (res == last_triple_it) // no matches found, we're done
// return max sequence found

// OK, we are at a start of a new sequence, find the end of it
auto seq_end = std::find_if_not(seq_beg, last_triple_it, is_alternating_triple);
if (std::distance(seq_beg, seq_end) > max_length_so_far)
// update max sequence so far
it = seq_end;  // instead of ++it, see comment inside loop
}
// return max sequence found


From these suggestions, it's easy to compose a general, flexible and almost certainly correct algorithm. Each step can be reasoned about in isolation. There is very little room for off-by-one errors. There is no unecessary copying of large vectors, just tuples of iterators.

Regarding your question for test cases: I would start with some simple stuff. Sequences with 0, 1 or 2 elements. Sequences with only alternating elements. Sequences with no alternating elements, etc.