a linear solution for this problem . although its more than O(n) but will never be O(n*2)..used DP to solve it
space used -O(2n) int ZigZagLength(vector<int> a){ int n=a.size(); int DP[n][2]; DP[0][0]=1; DP[0][1]=0; DP[1][0]=2; DP[1][1]=0; int j; for(int i=2;i<n;i++){ if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])==0){ DP[i][0]=DP[i-1][0]; DP[i][1]= i-1; } if((a[i]-a[i-1])*(a[i-1]-a[DP[i-1][1]])<0){ DP[i][0]=DP[i-1][0]+1; DP[i][1]= i-1; } else{ j = DP[i-1][1]; while(j>0){ if((a[i]-a[j])*(a[j]-a[DP[j][1]])<0){ DP[i][0]=max(DP[j][0]+1,DP[i-1][0]); if(DP[i][0]==DP[j][0]+1) DP[i][1]=j ; else DP[i][1]= i-1; break; }else j= DP[j][1]; } if(j==0){ DP[i][0]=DP[i-1][0]; DP[i][1]=DP[i-1][1]; } } } return DP[n-1][0]; } On Sun, Dec 18, 2011 at 11:04 AM, atul anand <atul.87fri...@gmail.com>wrote: > complexity of this algo is O(n) ..I guess it is better than dynamic > programming approach which is O(n^2). > > > On Sat, Dec 17, 2011 at 6:28 PM, atul anand <atul.87fri...@gmail.com>wrote: > >> please see the algo and let me know if i am doing it wrong:- >> >> toggle= arr[i+1] > arr[i]; >> subseq=0; >> >> for( i=0 ; i<len ;i++) >> { >> >> if ( toggle == 1) >> { >> if( arr[i+1] > arr[i]) >> { >> subseq=subseq+2; >> >> } >> >> toggle=0; >> } >> else >> { >> >> if(arr[i] > arr[i+1]) >> { >> >> subseq=subseq+2; >> >> } >> >> toggle=1; >> } >> >> >> } >> >> print subseq; >> >> >> On Fri, Dec 16, 2011 at 10:33 AM, Sangeeta <sangeeta15...@gmail.com>wrote: >> >>> Problem Statement >>> A sequence of numbers is called a zig-zag sequence if the differences >>> between successive numbers strictly alternate between positive and >>> negative. The first difference (if one exists) may be either positive >>> or negative. A sequence with fewer than two elements is trivially a >>> zig-zag sequence. >>> >>> For example, 1,7,4,9,2,5 is a zig-zag sequence because the differences >>> (6,-3,5,-7,3) are alternately positive and negative. In contrast, >>> 1,4,7,2,5 and 1,7,4,5,5 are not zig-zag sequences, the first because >>> its first two differences are positive and the second because its last >>> difference is zero. >>> >>> Given a sequence of integers, sequence, return the length of the >>> longest subsequence of sequence that is a zig-zag sequence. A >>> subsequence is obtained by deleting some number of elements (possibly >>> zero) from the original sequence, leaving the remaining elements in >>> their original order >>> >>> -- >>> 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. >>> >>> >> > -- > 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. > -- 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.