[algogeeks] Re: zig zag

[bittu]

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 algogeeks@googlegroups.com.
To unsubscribe from this group, send email to 
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at 
http://groups.google.com/group/algogeeks?hl=en.