#include <bits/stdc++.h>
using namespace std;
struct range {
int start;
int end;
range(int s, int e) {start=s; end=e;}
};
void find_longest_consecutive_numbers(vector<int>& N)
{
unordered_map<int,range> hash;
unordered_map<int,range>::iterator left, right;
range max_range(0,0);
int max_length=0;
for(int i=0; i<N.size(); i++) {
range r(N[i],N[i]);
left = hash.find(N[i]-1);
right = hash.find(N[i]+1);
// update range r
if( left!=hash.end() )
r.start = left->second.start;
if( right!=hash.end() )
r.end = right->second.end;
// update hash table
if( left!=hash.end() )
left->second.end = r.end;
if( right!=hash.end() )
right->second.start = r.start;
// insert range r
hash.insert(make_pair(N[i],r));
// check if this range was the longest
if( r.end-r.start+1 > max_length ) {
max_length = r.end-r.start+1;
max_range.start = r.start;
max_range.end = r.end;
}
}
printf("longest range = %d : %d\n", max_range.start, max_range.end);
}
int main(){
vector<int> arr={1,6,10,4,7,9,5} ;
find_longest_consecutive_numbers(arr);
return 0;
}
CiNpbmNsdWRlIDxiaXRzL3N0ZGMrKy5oPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwpzdHJ1Y3QgcmFuZ2UgewoJaW50IHN0YXJ0OwoJaW50IGVuZDsKCXJhbmdlKGludCBzLCBpbnQgZSkge3N0YXJ0PXM7IGVuZD1lO30KfTsKCnZvaWQgZmluZF9sb25nZXN0X2NvbnNlY3V0aXZlX251bWJlcnModmVjdG9yPGludD4mIE4pCnsKCXVub3JkZXJlZF9tYXA8aW50LHJhbmdlPiBoYXNoOwoJdW5vcmRlcmVkX21hcDxpbnQscmFuZ2U+OjppdGVyYXRvciBsZWZ0LCByaWdodDsKCglyYW5nZSBtYXhfcmFuZ2UoMCwwKTsKCWludCBtYXhfbGVuZ3RoPTA7CgoJZm9yKGludCBpPTA7IGk8Ti5zaXplKCk7IGkrKykgewkJCgkJcmFuZ2UgcihOW2ldLE5baV0pOwoKCQlsZWZ0ID0gaGFzaC5maW5kKE5baV0tMSk7CgkJcmlnaHQgPSBoYXNoLmZpbmQoTltpXSsxKTsKCQkKICAgICAgICAvLyB1cGRhdGUgcmFuZ2UgcgoJCWlmKCBsZWZ0IT1oYXNoLmVuZCgpICkgCgkJCXIuc3RhcnQgPSBsZWZ0LT5zZWNvbmQuc3RhcnQ7CgkJaWYoIHJpZ2h0IT1oYXNoLmVuZCgpICkKCQkJci5lbmQgPSByaWdodC0+c2Vjb25kLmVuZDsKCgkJLy8gdXBkYXRlIGhhc2ggdGFibGUKCQlpZiggbGVmdCE9aGFzaC5lbmQoKSApIAoJCQlsZWZ0LT5zZWNvbmQuZW5kID0gci5lbmQ7CgkJaWYoIHJpZ2h0IT1oYXNoLmVuZCgpICkKCQkJcmlnaHQtPnNlY29uZC5zdGFydCA9IHIuc3RhcnQ7CgoJCS8vIGluc2VydCByYW5nZSByCgkJaGFzaC5pbnNlcnQobWFrZV9wYWlyKE5baV0scikpOwoKCQkvLyBjaGVjayBpZiB0aGlzIHJhbmdlIHdhcyB0aGUgbG9uZ2VzdAoJCWlmKCByLmVuZC1yLnN0YXJ0KzEgPiBtYXhfbGVuZ3RoICkgewoJCQltYXhfbGVuZ3RoID0gci5lbmQtci5zdGFydCsxOwoJCQltYXhfcmFuZ2Uuc3RhcnQgPSByLnN0YXJ0OwoJCQltYXhfcmFuZ2UuZW5kID0gci5lbmQ7CgkJfQoJfQoKCXByaW50ZigibG9uZ2VzdCByYW5nZSA9ICVkIDogJWRcbiIsIG1heF9yYW5nZS5zdGFydCwgbWF4X3JhbmdlLmVuZCk7Cn0KaW50IG1haW4oKXsKIHZlY3RvcjxpbnQ+IGFycj17MSw2LDEwLDQsNyw5LDV9IDsKIGZpbmRfbG9uZ2VzdF9jb25zZWN1dGl2ZV9udW1iZXJzKGFycik7CiByZXR1cm4gMDsKfQo=