find the first longest ascending or descending sub-sequence in a given unsorted sequence by C++

Question

I am writing a C++ program that would find and print the first longest ascending or descending continuous subsequence for a vector of integers. For example, given a vector with

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

return 1,2,3,4

My code is as follows:

But, I do not know how to return the first optimal solution. For example, the above sequence has 1, 2, 4, 6 which is also 4 long. But, we only need to return 1,2,3,4.

bool findLong(const vector<int> v)
{
  if (v.size() <1)
    return false;
  if (v.size() == 1){
    cout << v[0] << endl;
    return true;
  }
  vector::const_iterator itr_left, itr_right;
  itr_left = v.begin();
  itr_right = v.begin()+1;
  bool ascending_flag ;
  int counter =0;
  if (*itr_right > *(itr_right-1)){
    bool ascending_flag = true;
    ++ascending_counter;    
  } 
  else{
    bool ascending_flag = false;
    ++descending_counter;
  }
  int longest = INT_MIN;
  Vector<int>::iterator longest_left = v.begin(), longest_right =v.begin(); 
  ++itr_right; 
  while (itr_right != v.end())
  {
   if (ascending_flag && *itr_right > *(itr_right-1))
     ++ascending_counter; 

   if (!ascending_flag&& *itr_right < *(itr_right-1))     
     ++descending_counter;       

   if  (ascending_flag&& *itr_right < *(itr_right-1))
   {
     if (ascending_counter > longest )
     {
        longest  = ascending_counter;
        longest_left = itr_left;
        longest_right = itr_right;
    }
    itr_left = itr_right;    
    ascending_counter = 0 ;  
    ascending_flag = false;
  }
  if  (ascending_flag && *itr_right > *(itr_right-1))
  {
    if (descending_counter > longest )
    {
        longest  = descending_counter;
        longest_left = itr_left;
        longest_right = itr_right;
    }       
    itr_left = itr_right;      
    descending_counter = 0 ;
    ascending_flag = true;
  }
  ++itr_right;
 }
 for_each( longest_left , longest_right, print);
 cout << endl;
}

Void print(int i)
{
  cout << i << " , " ;
}

Any comments are welcome !

Thanks !

Answer 1

Here are some thoughts:

1. If function is named "findX()", it should return X (say, pointer to the first element of the sequence or NULL, or index of the first element or -1). If function prints X, it should be named "printX()".
2. It's not clear whether you need ascending or strictly ascending sequence (i.e. is (1, 2, 2, 3) good for you or not).

3. You overcomplicate things. If you need first sequence, you just use reverse iterators and go from end to beginning, like this (I don't use iterators, but it should be clear how to include them):

   int maxLength=1, currentUp=1, currentDown=1; //Last element is sequence of 1 element
   size_t result = v.length()-1;
   for(size_t i = v.length()-1; i!=0; --i){
       if(v[i-1] > v[i]) {
           currentDown++; currentUp=0;
       } else if(v[i-1] < v[i]) {
           currentUp++; currentDown=0;
       } else {
           //Not clear what should happen, change may be needed
           currentUp++; currentDown++;
       }
   
       if(maxLength <= max(currentUp, currentDown)) {
           result = i-1;
           maxLength = max(currentUp, currentDown);
       }
   }
   
   return result;
   

Answer 2

You have lot of typo in your code: You hide the initialization of ascending_flag Your length count seems incorrect.

Following should work (as long as there aren't two neighbours with same values).

bool findLong(const vector<int>& v)
{
    if (v.empty())
        return false;
    if (v.size() == 1) {
        cout << v[0] << endl;
        return true;
    }
    vector<int>::const_iterator itr_left = v.begin();
    vector<int>::const_iterator itr_right = v.begin() + 1;
    vector<int>::const_iterator longest_left = itr_left;
    vector<int>::const_iterator longest_right = itr_right;
    bool ascending_flag = (*itr_right > *(itr_right - 1));

    for (++itr_right; itr_right != v.end(); ++itr_right)
    {
        if (ascending_flag ^ (*itr_right < *(itr_right - 1)))
        {
            if (itr_right - itr_left > longest_right - longest_left)
            {
                longest_left = itr_left;
                longest_right = itr_right;
            }
            itr_left = itr_right - 1;
            ascending_flag = !ascending_flag;
        }
    }
    for_each(longest_left, longest_right, print);
    cout << endl;
    return true;
}

Answer 3

Well, for starters, your function will always return true.

if (v.size() <1)
  return false;
if (v.size() == 1)
  cout << v[0] << endl;
return true;

should probably be

if (v.size() <1) {
  return false;

} else if (v.size() == 1) {
  cout << v[0] << endl;
  return true;
}