The longest consecutive sequence

/**97 Answers
Given an array of random numbers. Find the longest consecutive sequence.
For ex
Array 100 3 200 1 2 4
Ans 1 2 3 4
Array 101 2 3 104 5 103 9 102
Ans 101 102 103 104

Can we do it in one go on array using extra space??*/

/**On the one go, use a map to record the beginning and ending of a sub-sequence, merge two sub-sequences to
one. The counts are determined by ending-beginning. sequence representation: [beginning, ending]
*/

#include <map>
#include <vector>
#include <array>
#include <set>
#include <algorithm>
#include <iterator>
#include <iostream>
using namespace std;
class Solution{
public:
  vector<int> getLCS(vector<int> const& s){
    vector<int> beginning;//store beginnings of sub-sequences
    vector<int> ending;//store endings of sub-sequences
    for(int ii = 0; ii < s.size(); ++ii){
      int const number = s[ii];
      auto it_begin = find(beginning.begin(), beginning.end(), number+1);
      auto it_end = find(ending.begin(), ending.end(), number-1);
      if (it_end != ending.end() && it_begin != beginning.end()){//the number is a bridge
        //sew two sub-sequences together.
        int const high_seq_pos = distance(beginning.begin(), it_begin);
        (*it_end) = ending[high_seq_pos];
        beginning.erase(it_begin);
        ending.erase(ending.begin() + high_seq_pos);
        continue;
      }
      if (it_end != ending.end()){//can be appended after one existing sequence
        ++(*it_end);//should equal to number now.
        continue;
      }//it_end
      if( it_begin != beginning.end()){//can be the new beginning of one existing sequence
        --(*it_begin);//new begin should be number now
        continue;
      }
      //init case, just insert in the number
      beginning.push_back(number);
      ending.push_back(number);
    }//for ii
    int maxLCS = 0;
    int maxPos = 0;
    for(int ii = 0; ii < beginning.size(); ++ii){
      int const localLength = ending[ii] - beginning[ii];
      if (maxLCS < localLength){
        maxPos = ii;
        maxLCS = localLength;
      }
    }
    vector<int> result;
    result.reserve(maxLCS);
    for(int ii = beginning[maxPos]; ii <= ending[maxPos]; ++ii){
      result.push_back(ii);
    }
    return result;
  }//getLCS
};
int main(){
  cout<<"Hello"<<endl;
  Solution s;
  array<int, 6> a = {100,3,200,1,2,4};  
  vector<int> r = s.getLCS(vector<int>(a.begin(),a.end()));
  for(int ii = 0; ii < r.size(); ++ii){
    cout << r[ii] << endl;
  }
  cout<<endl<<endl;
  array<int, 8> b ={101, 2, 3, 104, 5, 103, 9, 102};
  r = s.getLCS(vector<int>(b.begin(), b.end()));
  for(int ii = 0; ii < r.size(); ++ii){
    cout << r[ii] << endl;
  }
  cout<<endl<<endl;
  array<int, 9> c ={6, 2, 8, 104, 8, 103, 9, 102,100};
  r = s.getLCS(vector<int>(c.begin(), c.end()));
  for(int ii = 0; ii < r.size(); ++ii){
    cout << r[ii] << endl;
  }

}