No , actually it's not ... it's O(n^2) , I misunderstood the
"subsequence" thing , it could be discontinuous .. we , then need to
find the maximum of dp[l] ...
the second term makes sure that the sign of the two quantities is
alternating i.e. positive or negative !
On Jan 29, 11:06 am, nishaanth <nishaant...@gmail.com> wrote:
> @above...can you please enlighten me about the second term in the dp
> expression
> And are you sure its O(n) ?
>
> On Fri, Jan 28, 2011 at 7:08 PM, sankalp srivastava <
>
>
>
>
>
> richi.sankalp1...@gmail.com> wrote:
> > This can be done in O(n) very easily , similar to Longest increasing
> > subsequence
>
> > Solution :-
>
> > dp[l]= maximum length of the zigzag sequence upto the length l
>
> > //At any position , the particular number in the array can either
> > extend the zigzag sequence containing the last element or it can start
> > one of it's own . So the recurrance becomes
>
> > dp[i]= max(dp[j]) ,and diff[A[p[j]]]^(A[i]-A[p[j]]&31)!=0 , j<i
>
> > find out the maximum in this array , it will get you the answer .
>
> > PS:- You can also check out the Topcoder tutorials .
>
> > On Jan 27, 7:41 pm, bittu <shashank7andr...@gmail.com> wrote:
> > > 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<algogeeks%2Bunsubscribe@googlegroups
> > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> S.Nishaanth,
> Computer Science and engineering,
> IIT Madras.
--
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.
