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 <[email protected]> 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 [email protected].
>
--
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 [email protected].
