## Dynamic Programming - Longest Zig Zag Sequence

### Problem

ZigZag - 2003 TCCC Semifinals 3

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.

Constraints

- sequence contains between 1 and 50 elements, inclusive.

- Each element of sequence is between 1 and 1000, inclusive.

Examples

{ 1, 7, 4, 9, 2, 5 }

Returns: 6

The entire sequence is a zig-zag sequence.

{ 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }

Returns: 7

There are several subsequences that achieve this length. One is 1,17,10,13,10,16,8.

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.

Constraints

- sequence contains between 1 and 50 elements, inclusive.

- Each element of sequence is between 1 and 1000, inclusive.

Examples

{ 1, 7, 4, 9, 2, 5 }

Returns: 6

The entire sequence is a zig-zag sequence.

{ 1, 17, 5, 10, 13, 15, 10, 5, 16, 8 }

Returns: 7

There are several subsequences that achieve this length. One is 1,17,10,13,10,16,8.

### Solution

int findLongZigZag(int *a, int size) {

if(size<=2) {

printf("%d\n", size);

return;

}

// to track alternate positive and negative sequence.

int *b = (int *)malloc(sizeof(int)*size);

// to track length of longest sequence till ith index.

int *s = (int *)malloc(sizeof(int)*size));

int i,j;

s[0]=1;

b[0]=a[0];

b[1]=a[1]-a[0];

s[1]=2;

for(i=2;i<size;i++) {

s[i]=2;

b[i]=0;

}

for(i=2;i<size;i++) {

for(j=1;j<i;j++) {

if(b[j]<0) {

if(a[i] > a[j] && s[i]<=s[j]+1) {

s[i]=s[j]+1;

b[i]=a[i]-a[j];

}

} else {

if(a[i] < a[j] && s[i]<=s[j]+1) {

s[i]=s[j]+1;

b[i]=a[i]-a[j];

}

}

}

if(b[i]==0) {

b[i]=a[i]-a[i-1];

}

}

return s[size-1];

}

## No comments:

## Post a Comment