Another Dynamic Programming

ZigZag Problem

This problem gives an input array of int asks to find the length of a longest subsequence in which the difference of successive numbers has opposite signs.

The problem took an extraordinary effort to register and find the recurrences and although I must have seen something like this before, breaking into the recurrence took too long. The recurrence I chose finally was :

 for an element at index i in the array, a longest subsequence can be either by having a greater number than element[i] or an element lesser than element[i]. So, there can be two kinds of sub-sequences for each element, one kind for which the element before the current is smaller and the other subsequence in which the element is larger. (Subsequence 1: element[i], the last element is greater than the one before it, Subsequence 2: element[i], the last element is less than the one before it)

The recurrence would turn out to be:   the maximum subsequence of kind 1 for element i would be the maximum subsequence of kind 2 for all elements before the index i and similarly max subsequence of kind 2 would be max subsequence of kind 1 for all elements before the index i. The length of a longest subsequence would hence be the maximum of the length of both kinds of the subsequences.

Here is the method I wrote recursively without bothering for speed.

 
 public int longestZigZagRec(int[] n, int index, boolean pos) {
  if(index==0)
   return 1;
  int posMax = 1,negMax = 1;
  if(pos) {
   for(int i=0;i<index;i++) 
    if(n[i] < n[index])
     posMax = max(longestZigZagRec( n, i, !pos) + 1, posMax);
  }
  else {
   for(int i=0;i<index;i++)
    if(n[i] > n[index])
     negMax = max(longestZigZagRec( n, i, !pos) + 1, negMax);
  }
  
  int temp = pos==true?posMax:negMax;
  //System.out.println(" from index "+ index+ " longest zigzap length is " + temp +" for "+ pos);
  return pos==true?posMax:negMax;

 }

I call the code like so:
  ZigZag z = new ZigZag();
int [] in = {20,10,1,7,4,9,2,5};
System.out.println(z.max(z.longestZigZagRec(in, in.length-1, true),z.longestZigZagRec(in, in.length-1, false)));