Re: [algogeeks] zig zag problem

2011-12-19 Thread atul anand
@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 :-

#includestdio.h

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;ilen;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;in;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 ankurga...@gmail.com 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 ankurga...@gmail.com 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(vectorint 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;in;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(j0){
 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.comwrote:

 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.comwrote:

 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 ; ilen ;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.comwrote:

 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 

Re: [algogeeks] zig zag problem

2011-12-19 Thread atul anand
@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.
 14327862
 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 atul.87fri...@gmail.comwrote:

 @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 :-

 #includestdio.h

 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;ilen;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;in;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 ankurga...@gmail.com 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 ankurga...@gmail.comwrote:

 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(vectorint 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;in;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(j0){
 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.comwrote:

 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.comwrote:

 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 ; ilen ;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.comwrote:

 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 

Re: [algogeeks] zig zag problem

2011-12-18 Thread atul anand
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 ; ilen ;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.comwrote:

 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

2011-12-18 Thread Ankur Garg
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(vectorint 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;in;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(j0){
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.comwrote:

 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.comwrote:

 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 ; ilen ;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.comwrote:

 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

2011-12-18 Thread Ankur Garg
@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 ankurga...@gmail.com 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(vectorint 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;in;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(j0){
 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.comwrote:

 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.comwrote:

 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 ; ilen ;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.comwrote:

 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

2011-12-17 Thread atul anand
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 ; ilen ;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.



[algogeeks] zig zag problem

2011-12-15 Thread Sangeeta
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.



Re: [algogeeks] zig zag problem

2011-12-15 Thread Azhar Hussain
It is dynamic programming.
Search in topcoder algo tutorials

On Dec 16, 2011 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.