@陈利人: #面试编程题#Given an unsorted array of integers, find the length of the longest consecutive ele\ ments sequence. Eg, given [100, 2, 1, 3], The longest consecutive elements sequence is [1, 2, 3].\ Return its length: 3. Your algorithm should run in O(n). （谢谢 @张成_ICT 推荐）

max_consecutive_sequence_len.cpp

#include <cstdio>
#include <vector>
#include <ext/hash_map>
#include <algorithm>

using namespace std;
using namespace __gnu_cxx;
typedef pair<int,int> pairii;
int max_consecutive_sequence_len(const vector<int> &vecArray)
{
  if (vecArray.empty())
      return 0;
      
  hash_map<int, pairii> map;
  for (size_t i = 0; i < vecArray.size(); ++i)
    {
      int n = vecArray[i];
      if (map.count(n))
        continue;
      pairii &pr = map[n];
      pr.first = pr.second = n;
      if (map.count(n-1))
        {
          pairii &left = map[n-1];
          pr.first = left.first;
        }
      if (map.count(n+1))
        {
          pairii &right = map[n+1];
          pr.second = right.second;
        }
      if (map.count(n-1))
        {
          pairii &left = map[n-1];
          left.second = pr.second;
        }
      if (map.count(n+1))
        {
          pairii &right = map[n+1];
          right.first = pr.first;
	}
    }
  int maxLen = 1;
  for (size_t i = 0; i < vecArray.size(); ++i)
   {
      int n = vecArray[i];
      if (map.count(n))
        {
          int len = map[n].second - map[n].first + 1;
          if (len > maxLen)
            maxLen = len;
        }
    }
  return maxLen;
}

int main()
{
  vector<int> v;
  int n;
  while(scanf("%d", &n) == 1)
    v.push_back(n);

  printf("%d\n", max_consecutive_sequence_len(v));

  return 0;
}