TopCoder – Collegiate Challenge Tournament – 2003 – Semifinals 3 – 300

Problem Statement : TopCoder – Collegiate Challenge Tournament – 2003 – Semifinals 3 – 300

public class ZigZag {
	public int longestZigZag(int[] a) {
		int[] L = new int[a.length], d= new int[a.length];
		int maxL = 1, max = 1, maxJ = 0; L[0] = 1;
		for (int i = 1; i < a.length; i++) {
			L[i] = 1; maxL = 0; maxJ = 0;
			for (int j = 0; j < i; j++) {
				if ((a[i] > a[j] && d[j] <= 0) || (a[i] < a[j] && d[j] >= 0)) {
					L[i] = L[maxJ] + 1;
					maxJ = j;
				}
			}
			if (L[maxL] < L[i]) {
				d[i] = a[i] - a[maxJ];
				max = L[i];
			}
		}
		return max;
	}
}
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: