title: How to reduce the time complexity to find the longest zigzag sequence?
body: <p>I was trying to solve the problem zig zag sequences on top coder.The time complexity of my code is O(n*n). How can I reduce it to O(n) or O(nlog (n))
  Pseudo code or explanation of the algorithm will be really helpful to me
  Here is the problem statement.
  Problem Statement</p>
  
  <blockquote>
    <p>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.</p>
    
    <p>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.</p>
    
    <p>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.</p>
  </blockquote>
  
  <p>And here is my code</p>
  
  <pre><code>#include &lt;iostream&gt;
  #include&lt;vector&gt;
  #include&lt;cstring&gt;
  #include&lt;cstdio&gt;
  using namespace std;
  
  class ZigZag
  {
    public:
    int dp[200][2];
    void print(int n)
    {
        for(int i=0;i&lt;n;i++)
        {
            cout&lt;&lt;dp[i][0]&lt;&lt;endl;
        }
    }
    int longestZigZag(vector&lt;int&gt; a)
    {
        int n=a.size();
        //int dp[n][2];
        for(int i=0;i&lt;n;i++)
        {
            cout&lt;&lt;a[i]&lt;&lt;" "&lt;&lt;"\t";
        }
        cout&lt;&lt;endl;
        memset(dp,sizeof(dp),0);
        dp[0][1]=dp[0][0]=1;
        for(int i=1;i&lt;n;i++)
        {
              dp[i][1]=dp[i][0]=1;
  
              for(int j=0;j&lt;i;j++)
              {
                  if(a[i]&lt;a[j])
                  {
                     dp[i][0]=max(dp[j][1]+1,dp[i][0]);
                  }
                 if(a[j]&lt;a[i])
                 {
                      dp[i][1]=max(dp[j][0]+1,dp[i][1]);
                 }
              }
              cout&lt;&lt;dp[i][1]&lt;&lt;"\t"&lt;&lt;dp[i][0]&lt;&lt;" "&lt;&lt;i&lt;&lt;endl;
              //print(n);
        }
        cout&lt;&lt;dp[n-1][0]&lt;&lt;endl;
        return max(dp[n-1][0],dp[n-1][1]);
    }
  };
  </code></pre>