fork(2) download
  1.  
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. struct range {
  5. int start;
  6. int end;
  7. range(int s, int e) {start=s; end=e;}
  8. };
  9.  
  10. void find_longest_consecutive_numbers(vector<int>& N)
  11. {
  12. unordered_map<int,range> hash;
  13. unordered_map<int,range>::iterator left, right;
  14.  
  15. range max_range(0,0);
  16. int max_length=0;
  17.  
  18. for(int i=0; i<N.size(); i++) {
  19. range r(N[i],N[i]);
  20.  
  21. left = hash.find(N[i]-1);
  22. right = hash.find(N[i]+1);
  23.  
  24. // update range r
  25. if( left!=hash.end() )
  26. r.start = left->second.start;
  27. if( right!=hash.end() )
  28. r.end = right->second.end;
  29.  
  30. // update hash table
  31. if( left!=hash.end() )
  32. left->second.end = r.end;
  33. if( right!=hash.end() )
  34. right->second.start = r.start;
  35.  
  36. // insert range r
  37. hash.insert(make_pair(N[i],r));
  38.  
  39. // check if this range was the longest
  40. if( r.end-r.start+1 > max_length ) {
  41. max_length = r.end-r.start+1;
  42. max_range.start = r.start;
  43. max_range.end = r.end;
  44. }
  45. }
  46.  
  47. printf("longest range = %d : %d\n", max_range.start, max_range.end);
  48. }
  49. int main(){
  50. vector<int> arr={1,6,10,4,7,9,5} ;
  51. find_longest_consecutive_numbers(arr);
  52. return 0;
  53. }
  54.  
Success #stdin #stdout 0s 16064KB
stdin
Standard input is empty
stdout
longest range = 4 : 7