title: Dynamic programming: Find longest subsequence that is zig zag
body: <p>Can anyone please help me understand the core logic behind the solution to a problem mentioned at <a href="http://www.topcoder.com/stat?c=problem_statement&amp;pm=1259&amp;rd=4493" rel="nofollow noreferrer">http://www.topcoder.com/stat?c=problem_statement&amp;pm=1259&amp;rd=4493</a></p>
  
  <p>A zig zag sequence is one that alternately increases and decreases. So, 1 3 2 is zig zag, but 1 2 3 is not. Any sequence of one or two elements is zig zag. We need to find the longest zig zag subsequence in a given sequence. Subsequence means that it is not necessary for elements to be contiguous, like in the longest increasing subsequence problem. So, 1 3 5 4 2 could have 1 5 4 as a zig zag subsequence. We are interested in the longest one.</p>
  
  <p>I understand that this is a dynamic programming problem and it is very similar to <a href="https://stackoverflow.com/questions/2631726/how-to-determine-the-longest-increasing-subsequence-using-dynamic-programming">How to determine the longest increasing subsequence using dynamic programming?</a>.</p>
  
  <p>I think any solution will need an outer loop that iterates over sequences of different lengths, and the inner loop will have to iterate over all sequences.</p>
  
  <p>We will store the longest zig zag sequence ending at index i in another array, say dpStore at index i. So, intermediate results are stored, and can later be reused. This part is common to all Dynamic programming problems. Later we find the global maximum and return it.</p>
  
  <p>My solution is definitely wrong, pasting here to show what I've so far. I want to know where I went wrong.</p>
  
  <pre><code>    private int isZigzag(int[] arr)
  {
      int max=0;
      int maxLength=-100;
      int[] dpStore = new int[arr.length];
  
      dpStore[0]=1;
  
      if(arr.length==1)
      {
          return 1;
      }
      else if(arr.length==2)
      {
          return 2;
      }
      else 
      {           
          for(int i=3; i&lt;arr.length;i++)
          {
              maxLength=-100;
              for(int j=1;j&lt;i &amp;&amp; j+1&lt;=arr.length; j++)
              {
                  if(( arr[j]&gt;arr[j-1] &amp;&amp; arr[j]&gt;arr[j+1])
                      ||(arr[j]&lt;arr[j-1] &amp;&amp; arr[j]&lt;arr[j+1]))
                  {
                      maxLength = Math.max(dpStore[j]+1, maxLength);
                  }
              }
              dpStore[i]=maxLength;               
          }
      }
      max=-1000;
      for(int i=0;i&lt;arr.length;i++)
      {
          max=Math.max(dpStore[i],max);
      }
      return max; 
  }
  </code></pre>