O(n) is straight forward
bool increase = true;
int j = 0;
result[j++]=a[0];
for (int i=1;i<n;i++)
{
if ((increase)
{
if (result[j-1]<a[i]))
{
result[j++] = a[i];
increase = false;
}
}
else {
if (result[j-1] >a[i]))
{
result[j++] = a[i];
increase = true;
}
}
}
What i was thinking is to find the number of peaks and valleys through
binary search thereby using log(n) solution not able to conceptualize it
this way (:.
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Fri, Jun 8, 2012 at 3:47 PM, Ratan <[email protected]> wrote:
> Given a list of integers n, we have to find the length of largest
> zigazg subsequence in the list.... i.e,zigzag subsequence is defined
> as "if the first number is increasing then the 2nd one should be
> decreasing or vice versa...... "
>
> for eg : if list[n]={1,10,5,9,8,12,20} then,
>
> largest zigzag subsequence will be : {1,10,5,9,8,12} or
> {1,10,5,9,8,20} and length will be=6;
>
>
> --
> --
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
