well I found it as it Can be Done in O(n). but with additional space
O(n)
here program is written in Java
public class ZigZag
{
public int longestZigZag(int[] sequence)
{
if (sequence.length==1) return 1;
if (sequence.length==2) return 2;
int[] diff = new int[sequence.length-1];
for (int i=1;i<sequence.length;i++)
{
diff[i-1]=sequence[i]-sequence[i-1];
}
//90% Program is done here it self. by looking at the sign if
alternative number in auxiliary array we can count longest zigzag
array
int sign=sign(diff[0]);
int count=0;
if (sign!=0)
count=1;
for (int i=1;i<diff.length;i++)
{
int nextsign=sign(diff[i]);
if (sign*nextsign==-1){
sign=nextsign;
count++;
}
}
return count+1;
}
public int sign(int a)
{
if (a==0) return 0;
return a/Math.abs(a);
}
public static void main(String[] args)
{
ZigZag z = new ZigZag();
System.out.println(z.longestZigZag(new int[] { 1, 7, 4, 9, 2, 5 }));
System.out.println(z.longestZigZag(new int[] { 1, 17, 5, 10, 13, 15,
10, 5, 16, 8 }));
}
}
Try for Inplace
Thanks & Regards
Shashank Mani ""The best way to escape from a problem is to solve it."
--
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.
