How to reduce the time complexity to find the longest zigzag sequence?

Question

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

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.

And here is my code

#include <iostream>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;

class ZigZag
{
  public:
  int dp[200][2];
  void print(int n)
  {
      for(int i=0;i<n;i++)
      {
          cout<<dp[i][0]<<endl;
      }
  }
  int longestZigZag(vector<int> a)
  {
      int n=a.size();
      //int dp[n][2];
      for(int i=0;i<n;i++)
      {
          cout<<a[i]<<" "<<"\t";
      }
      cout<<endl;
      memset(dp,sizeof(dp),0);
      dp[0][1]=dp[0][0]=1;
      for(int i=1;i<n;i++)
      {
            dp[i][1]=dp[i][0]=1;

            for(int j=0;j<i;j++)
            {
                if(a[i]<a[j])
                {
                   dp[i][0]=max(dp[j][1]+1,dp[i][0]);
                }
               if(a[j]<a[i])
               {
                    dp[i][1]=max(dp[j][0]+1,dp[i][1]);
               }
            }
            cout<<dp[i][1]<<"\t"<<dp[i][0]<<" "<<i<<endl;
            //print(n);
      }
      cout<<dp[n-1][0]<<endl;
      return max(dp[n-1][0],dp[n-1][1]);
  }
};

Answer 1

This is a purely theoretical solution. This is how you would solve it if you would be asked for it in an academical environment, standing next to the chalkboard.

The solution to the problem can be created using dynamic programming:

The subproblem has the form of: if I have an element x of the sequence, what is the longest subsequence that is ending on that element?

Then you can work out your solution using recursive calls, which should look something like this (the directions of the relations might be wrong, I haven't checked it):

S - given sequence (array of integers)
P(i), Q(i) - length of the longest zigzag subsequence on elements S[0 -> i] inclusive (the longest sequence that is correct, where S[i] is the last element)

P(i) = {if i == 0 then 1
   {max(Q(j) if A[i] < A[j] for every 0 <= j < i)


Q(i) = {if i == 0 then 0  #yields 0 because we are pedantic about "is zig the first relation, or is it zag?". If we aren't, then this can be a 1.
   {max(P(j) if A[i] > A[j] for every 0 <= j < i)

This should be O(n) with the right memoization (storing each output of Q(i) and P(i)), because each subproblem is only computed once: n*|P| + n*|Q|.

These calls return the length of the solution - the actual result can be found by storing "parent pointer" whenever a max value is found, and then traversing backwards on these pointers.

You can avoid the recursion simply by substituting function calls with array lookups: P[i] and Q[i], and using a for loop.

Answer 2

You can solve this problem in O(n) time and O(n) extra space.

Algorithm goes as follows.

1. Store the difference of alternative term in new array of size n-1
2. Now traverse the new array and just check whether the product of alternative term is less then zero or not.
3. Increment result accordingly. If while traversing you find that array is product is more than zero in that case you store the result and again start counting for the rest of the element in difference array.
4. Find the maximum among them store it into result, and return (result+1)

Here is it's implementation in C++

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    int n;
    cin>>n;
    vector<int> data(n);
    for(int i = 0; i < n; i++)
        cin>>data[i];
    vector<int> diff(n-1);
    for(int i = 1; i < n; i++)
        diff[i-1] = data[i]-data[i-1];
    int res = 1;
    if( n < 2)
        cout<<res<<"\n";
    else
    {
        int temp_idx = 0;
        for(int i = 1; i < n-1; i++)
        {
            if(diff[i]*diff[i-1] < 0)
            {
                temp_idx++;
                res++;
            }
            else
            {
                res = max(res,temp_idx);
                temp_idx = 1;
            }
        }
        cout<<res+1<<"\n";
    }
    return 0;
}

Answer 3

U can do it in O(n) using a greedy approach. Take the first non-repeating number - this is the first number of your zigzag subsequence. Check whether the next number in the array is lesser than or greater than the first number.

Case 1: If lesser, check the next element to that and keep going till you find the least element (ie) the element after that would be greater than the previous element. This would be your second element.

Case 2: If greater, check the next element to that and keep going till you find the greatest element (ie) the element after that would be lesser than the previous element. This would be your second element.

If u have used Case 1 to find the second element, use Case 2 to find the third element or vice-versa. Keep alternating between these two cases till u have no more elements in the original sequence. The resultant numbers u get would form the longest zigzag subsequence.

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

The resulting subsequence:

1 -> 1,17 (Case 2) -> 1,17,5 (Case 1) -> 1,17,5,15 (Case 2) -> 1,17,5,15,5 (Case 1) -> 1,17,5,15,5,16 (Case 2) -> 1,17,5,15,5,16,8 (Case 1)

Hence the length of the longest zigzag subsequence is 7.

U can refer to sjelkjd's solution for an implementation of this idea.

Answer 4

You can use RMQs to remove the inner for-loop. When you find the answer for dp[i][0] and dp[i][1], save it in two RMQ trees - say, RMQ₀ and RMQ₁ - just like you're doing now with the two rows of the dp array. So, when you calculate dp[i][0], you put the value dp[i][0] on position a[i] in RMQ₀, meaning that there is a zig-zag sequence with length dp[i][0] ending increasingly with number a[i].

Then, in order to calculate dp[i + 1][0], you don't have to loop through all the numbers between 0 and i. Instead, you can query RMQ₀ for the largest number on position > a[i + 1]. This will give you the longest zig-zag subsequence ending with a number larger than the current one - i.e. the longest one that can be continued decreasingly with the number a[i + 1]. Then you can do the same for RMQ₁ for the other half of the zig-zag subsequences.

Since you can implement dynamic RMQ with query complexity of O(log N), this gives you an overall complexity of O(N log N).

Answer 5

As the subsequence should not be necessarily contiguous you can't make it O(n). In a worst case the complexity is O(2^n). Howewer, I did some checks to cut off subtrees as soon as possible.

int maxLenght;

void test(vector<int>& a, int sign, int last, int pos, int currentLenght) {
    if (maxLenght < currentLenght) maxLenght = currentLenght;
    if (pos >= a.size() || pos >= a.size() + currentLenght - maxLenght) return;
    if (last != a[pos] && (last - a[pos] >= 0) != sign) 
        test(a,!sign,a[pos],pos+1,currentLenght+1);
    test(a,sign,last,pos+1,currentLenght);
}

int longestZigZag(vector<int>& a) {
    maxLenght = 0;
    test(a,0,a[0],1,1);
    test(a,!0,a[0],1,1);
    return maxLenght;
}