Re: [algogeeks] zig zag problem
hi i gave anser of longets sequence if there are more than one then I only
print one
On Tue, Dec 20, 2011 at 12:31 PM, atul anand wrote:
> @UTKARSH :
>
> it should be 1 4 3 7 6
>
> why are you skipping 3 even when 143 is in zig zag sequence.
>
> On Tue, Dec 20, 2011 at 11:26 AM, UTKARSH SRIVASTAV <
> usrivastav...@gmail.com> wrote:
>
>> hi i want to know whether this is right
>> suppose array is : 1,4,3,2,7,8,6,2
>> we just find where sign changes and take the first element of sign change
>> and we can take last element.
>> 1<4>3>2<7<8>6>2
>> so answer should be 1 4 2 8 2
>> correct me if i am wrong
>>
>> On Mon, Dec 19, 2011 at 12:26 PM, atul anand wrote:
>>
>>> @Ankur :
>>>
>>> yeah rite it wont work i have modified my algo and used many test
>>> cases , it is giving rite output.
>>> could you catch any test case for which it would fail.
>>> here is the updated code :-
>>>
>>> #include
>>>
>>> int findSeqLen(int arr[],int len,int subseq)
>>> {
>>>
>>> int i=0,flag1,flag2,toggle;
>>> int lastIndex=0;
>>> toggle=arr[i+1] > arr[i];
>>> flag1=toggle;
>>> flag2=!flag1;
>>>
>>> if(len <= 2)
>>> {
>>> return 0;
>>>
>>> }
>>>
>>> for(i=0;i>> {
>>>
>>> if(i==len-1)
>>> {
>>> break;
>>> }
>>> if(toggle==1)
>>> {
>>>
>>> if(arr[i+1] > arr[i] && arr[lastIndex] < arr[i+1] &&
>>> flag1==1)
>>> {
>>> subseq++;
>>> flag1=0;
>>> flag2=1;
>>> toggle=0;
>>> lastIndex=i+1;
>>> }
>>> printf("\n\nin toggle = 1");
>>> printf("\n i = %d , lastIndex = %d , subseq =
>>> %d",i,lastIndex,subseq);
>>> }
>>> else
>>> {
>>>
>>> if(arr[i] > arr[i+1] && arr[lastIndex] > arr[i+1] &&
>>> flag2==1)
>>> {
>>> subseq++;
>>> flag2=0;
>>> flag1=1;
>>> toggle=1;
>>> lastIndex=i+1;
>>> }
>>>
>>> printf("\n\nin toggle = 0");
>>> printf("\n i = %d , lastIndex = %d , subseq =
>>> %d",i,lastIndex,subseq);
>>>
>>>
>>>
>>> }
>>>
>>> }
>>>
>>>
>>> return subseq;
>>> }
>>>
>>>
>>> int main()
>>> {
>>> int arr[80],i,j,n,ls=1;
>>>
>>> printf("\nNumber of elements to be entered = ");
>>> scanf("%d",&n);
>>>
>>> for(i=0;i>> {
>>> printf("\nEnter Number = ");
>>> scanf("%d",&arr[i]);
>>> }
>>>
>>>
>>> ls=findSeqLen(arr,n,ls);
>>> printf("\n\nSubsequence len = %d\n\n",ls);
>>>
>>> }
>>>
>>>
>>>
>>>
>>> On Mon, Dec 19, 2011 at 1:19 AM, Ankur Garg wrote:
>>>
@Atul ur solution is wrong
It seems u r comparing just the neighbouring elements .
The question is not to find the contiguous zig-zag sequence but longest
subsequence
Also even in case of contiguous sequence ur solution will not print the
correct length
like for 6 7 4 ur solution will print answer as 4 whereas in the answer
should be 3
Regards
Ankur
On Mon, Dec 19, 2011 at 1:16 AM, Ankur Garg wrote:
> 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 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 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
> 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
>> 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>> {
>>>
>>>if ( toggle == 1)
>>>{
>>>if( arr[i+1] > arr[i])
>>>{
>>> subseq=subseq+2;
>>>
>>>}
>>>
>>>toggle=0;
>>>}
>>>else
>>>{
>>>
>>> if(arr[i] > arr[i+1])
>>>
Re: [algogeeks] zig zag problem
@UTKARSH :
it should be 1 4 3 7 6
why are you skipping 3 even when 143 is in zig zag sequence.
On Tue, Dec 20, 2011 at 11:26 AM, UTKARSH SRIVASTAV wrote:
> hi i want to know whether this is right
> suppose array is : 1,4,3,2,7,8,6,2
> we just find where sign changes and take the first element of sign change
> and we can take last element.
> 1<4>3>2<7<8>6>2
> so answer should be 1 4 2 8 2
> correct me if i am wrong
>
> On Mon, Dec 19, 2011 at 12:26 PM, atul anand wrote:
>
>> @Ankur :
>>
>> yeah rite it wont work i have modified my algo and used many test
>> cases , it is giving rite output.
>> could you catch any test case for which it would fail.
>> here is the updated code :-
>>
>> #include
>>
>> int findSeqLen(int arr[],int len,int subseq)
>> {
>>
>> int i=0,flag1,flag2,toggle;
>> int lastIndex=0;
>> toggle=arr[i+1] > arr[i];
>> flag1=toggle;
>> flag2=!flag1;
>>
>> if(len <= 2)
>> {
>> return 0;
>>
>> }
>>
>> for(i=0;i> {
>>
>> if(i==len-1)
>> {
>> break;
>> }
>> if(toggle==1)
>> {
>>
>> if(arr[i+1] > arr[i] && arr[lastIndex] < arr[i+1] && flag1==1)
>> {
>> subseq++;
>> flag1=0;
>> flag2=1;
>> toggle=0;
>> lastIndex=i+1;
>> }
>> printf("\n\nin toggle = 1");
>> printf("\n i = %d , lastIndex = %d , subseq =
>> %d",i,lastIndex,subseq);
>> }
>> else
>> {
>>
>> if(arr[i] > arr[i+1] && arr[lastIndex] > arr[i+1] && flag2==1)
>> {
>> subseq++;
>> flag2=0;
>> flag1=1;
>> toggle=1;
>> lastIndex=i+1;
>> }
>>
>> printf("\n\nin toggle = 0");
>> printf("\n i = %d , lastIndex = %d , subseq =
>> %d",i,lastIndex,subseq);
>>
>>
>>
>> }
>>
>> }
>>
>>
>> return subseq;
>> }
>>
>>
>> int main()
>> {
>> int arr[80],i,j,n,ls=1;
>>
>> printf("\nNumber of elements to be entered = ");
>> scanf("%d",&n);
>>
>> for(i=0;i> {
>> printf("\nEnter Number = ");
>> scanf("%d",&arr[i]);
>> }
>>
>>
>> ls=findSeqLen(arr,n,ls);
>> printf("\n\nSubsequence len = %d\n\n",ls);
>>
>> }
>>
>>
>>
>>
>> On Mon, Dec 19, 2011 at 1:19 AM, Ankur Garg wrote:
>>
>>> @Atul ur solution is wrong
>>> It seems u r comparing just the neighbouring elements .
>>> The question is not to find the contiguous zig-zag sequence but longest
>>> subsequence
>>> Also even in case of contiguous sequence ur solution will not print the
>>> correct length
>>> like for 6 7 4 ur solution will print answer as 4 whereas in the answer
>>> should be 3
>>>
>>> Regards
>>> Ankur
>>>
>>>
>>> On Mon, Dec 19, 2011 at 1:16 AM, Ankur Garg wrote:
>>>
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 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>>> 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
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
> 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> {
>>
>>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
>> wrote:
>>
>>> Problem Statement
>>> A sequence of numbers is calle
Re: [algogeeks] zig zag problem
hi i want to know whether this is right
suppose array is : 1,4,3,2,7,8,6,2
we just find where sign changes and take the first element of sign change
and we can take last element.
1<4>3>2<7<8>6>2
so answer should be 1 4 2 8 2
correct me if i am wrong
On Mon, Dec 19, 2011 at 12:26 PM, atul anand wrote:
> @Ankur :
>
> yeah rite it wont work i have modified my algo and used many test
> cases , it is giving rite output.
> could you catch any test case for which it would fail.
> here is the updated code :-
>
> #include
>
> int findSeqLen(int arr[],int len,int subseq)
> {
>
> int i=0,flag1,flag2,toggle;
> int lastIndex=0;
> toggle=arr[i+1] > arr[i];
> flag1=toggle;
> flag2=!flag1;
>
> if(len <= 2)
> {
> return 0;
>
> }
>
> for(i=0;i {
>
> if(i==len-1)
> {
> break;
> }
> if(toggle==1)
> {
>
> if(arr[i+1] > arr[i] && arr[lastIndex] < arr[i+1] && flag1==1)
> {
> subseq++;
> flag1=0;
> flag2=1;
> toggle=0;
> lastIndex=i+1;
> }
> printf("\n\nin toggle = 1");
> printf("\n i = %d , lastIndex = %d , subseq =
> %d",i,lastIndex,subseq);
> }
> else
> {
>
> if(arr[i] > arr[i+1] && arr[lastIndex] > arr[i+1] && flag2==1)
> {
> subseq++;
> flag2=0;
> flag1=1;
> toggle=1;
> lastIndex=i+1;
> }
>
> printf("\n\nin toggle = 0");
> printf("\n i = %d , lastIndex = %d , subseq =
> %d",i,lastIndex,subseq);
>
>
>
> }
>
> }
>
>
> return subseq;
> }
>
>
> int main()
> {
> int arr[80],i,j,n,ls=1;
>
> printf("\nNumber of elements to be entered = ");
> scanf("%d",&n);
>
> for(i=0;i {
> printf("\nEnter Number = ");
> scanf("%d",&arr[i]);
> }
>
>
> ls=findSeqLen(arr,n,ls);
> printf("\n\nSubsequence len = %d\n\n",ls);
>
> }
>
>
>
>
> On Mon, Dec 19, 2011 at 1:19 AM, Ankur Garg wrote:
>
>> @Atul ur solution is wrong
>> It seems u r comparing just the neighbouring elements .
>> The question is not to find the contiguous zig-zag sequence but longest
>> subsequence
>> Also even in case of contiguous sequence ur solution will not print the
>> correct length
>> like for 6 7 4 ur solution will print answer as 4 whereas in the answer
>> should be 3
>>
>> Regards
>> Ankur
>>
>>
>> On Mon, Dec 19, 2011 at 1:16 AM, Ankur Garg wrote:
>>
>>> 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 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>> 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 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 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 {
>
>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 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 a
Re: [algogeeks] zig zag problem
@Ankur :
yeah rite it wont work i have modified my algo and used many test cases
, it is giving rite output.
could you catch any test case for which it would fail.
here is the updated code :-
#include
int findSeqLen(int arr[],int len,int subseq)
{
int i=0,flag1,flag2,toggle;
int lastIndex=0;
toggle=arr[i+1] > arr[i];
flag1=toggle;
flag2=!flag1;
if(len <= 2)
{
return 0;
}
for(i=0;i arr[i] && arr[lastIndex] < arr[i+1] && flag1==1)
{
subseq++;
flag1=0;
flag2=1;
toggle=0;
lastIndex=i+1;
}
printf("\n\nin toggle = 1");
printf("\n i = %d , lastIndex = %d , subseq =
%d",i,lastIndex,subseq);
}
else
{
if(arr[i] > arr[i+1] && arr[lastIndex] > arr[i+1] && flag2==1)
{
subseq++;
flag2=0;
flag1=1;
toggle=1;
lastIndex=i+1;
}
printf("\n\nin toggle = 0");
printf("\n i = %d , lastIndex = %d , subseq =
%d",i,lastIndex,subseq);
}
}
return subseq;
}
int main()
{
int arr[80],i,j,n,ls=1;
printf("\nNumber of elements to be entered = ");
scanf("%d",&n);
for(i=0;i wrote:
> @Atul ur solution is wrong
> It seems u r comparing just the neighbouring elements .
> The question is not to find the contiguous zig-zag sequence but longest
> subsequence
> Also even in case of contiguous sequence ur solution will not print the
> correct length
> like for 6 7 4 ur solution will print answer as 4 whereas in the answer
> should be 3
>
> Regards
> Ankur
>
>
> On Mon, Dec 19, 2011 at 1:16 AM, Ankur Garg wrote:
>
>> 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 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> 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 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 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>>> {
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 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
>
Re: [algogeeks] zig zag problem
@Atul ur solution is wrong
It seems u r comparing just the neighbouring elements .
The question is not to find the contiguous zig-zag sequence but longest
subsequence
Also even in case of contiguous sequence ur solution will not print the
correct length
like for 6 7 4 ur solution will print answer as 4 whereas in the answer
should be 3
Regards
Ankur
On Mon, Dec 19, 2011 at 1:16 AM, Ankur Garg wrote:
> 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 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 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 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 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>> {
>>>
>>>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 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.
Re: [algogeeks] zig zag problem
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 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;i0){
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 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 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> {
>>
>>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 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.
Re: [algogeeks] zig zag problem
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 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 {
>
>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 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.
Re: [algogeeks] zig zag problem
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 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 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.
Re: [algogeeks] zig zag problem
It is dynamic programming. Search in topcoder algo tutorials On Dec 16, 2011 10:33 AM, "Sangeeta" 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.
[algogeeks] zig zag problem
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.
