I think this the most optimized code i have writen :
#include <iostream>
#include <vector>
#include <map>
using namespace std;
int longest_sequence(vector<int> &nums) {
map<int,bool> mp;
int count;
int max = -9999;
int n = 0;
for(unsigned int i = 0; i < nums.size(); i++) {
mp[nums[i]] = true;
}
for(unsigned int i =0;i<nums.size();i++) {
n = nums[i];
mp.erase(n);
count = 1;
while(mp.find(n+1)!= mp.end()) {
count++;
mp.erase(n+1);
n++;
}
n = nums[i];
while(mp.find(n-1)!= mp.end()) {
count++;
mp.erase(n-1);
n--;
}
if(count > max) {
max = count;
}
}
return max;
}
int main() {
// your code goes here
cout << "Jai Ganesha";
vector<int> vc;
vc.push_back(5);
vc.push_back(20);
vc.push_back(45);
vc.push_back(3);
vc.push_back(98);
vc.push_back(4);
vc.push_back(21);
vc.push_back(1);
vc.push_back(99);
vc.push_back(2);
cout << endl << longest_sequence(vc);
return 0;
}
NIshant Pandey
Cell : 9911258345
Voice Mail : +91 124 451 2130
On Mon, Jan 27, 2014 at 4:29 PM, Amol Sharma <amolsharm...@gmail.com> wrote:
> Given an array of positive numbers arranged in any order. You have to find
> the length of longest continuos(difference of +1, -1) sequence in the array.
>
> for eg.
> A[] = *5*, 20, 45, *3*, 98, *4*, 21, *1*, 99, *2*
>
> then longest continuos subsequence is [1, 2, 3, 4, 5] and hence the output
> should be *"5"*, the length of this sequence.
>
> Other Continuos sequence are -
>
> [20, 21]
> [45]
> [98, 99]
> [21]
>
> A[i] can be > 10^6, so hashing is not an option.
>
> Possible Approach is by sorting and time complexity will be O(nlogn).
>
> Does anyone have better approach for this ?
>
>
>
> --
> Thanks and Regards,
> Amol Sharma
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to algogeeks+unsubscr...@googlegroups.com.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
