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 <[email protected]>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 <[email protected]>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 <[email protected]>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 [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.
>
--
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.
