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.
