The longest alternating sequence in C++

The first line of the input stream contains integer n. The second line contains n (1 a[i' + 1]) || (a[i' - 1] > a[i'] && a[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 =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 findLongestAlternantSequence(std::vector &inputArray)
{
if (inputArray.size() == 1 || inputArray.size() == 2)
return inputArray;

std::vector arrayOfDifferences;

for (size_t i = 0; i 0) ? 1 : 0);
}

std::vector 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 > seq;
std::vector v1;
std::vector 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 = seq[0][k])
{
++k;
if ( k == seq[0].size())
{
k = 0;
++s;
}
}
if (s < seq[1].size())
{
longestAlternantSequence.push_back(seq[1][s]);
}

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 altSubsequence(const std::vector &input) {
    if (input.size()  subsequenceLength[] = {
        std::vector(input.size(), 1),
        std::vector(input.size(), 1)
    };
    std::vector nextElement[] = {
        std::vector(input.size(), 0),
        std::vector(input.size(), 0)
    };
    size_t maxSubsequenceLength[] = { 1, 1 };

    for (int i = input.size() - 1; i >= 0; --i) {
        for (size_t dir = DESCENDING; dir  input[j])
                                        : (input[i]  maxSubsequenceLength[dir]) {
                            maxSubsequenceLength[dir] = subsequenceLength[dir][i];
                        }
                        if (subsequenceLength[dir][i] == 1 + maxSubsequenceLength[!dir]) {
                            break;
                        }
                    }
                }
            }
        }
    }

    std::vector 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 }

• 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.

• 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.

• 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.

• 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.

• 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.

• 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.

• 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-fi

StackExchange Code Review Q#31842, answer score: 4