如何减少时间复杂度,找到最长的锯齿形序列？

Question

我试图在顶级编码器上解决问题zig zag序列.我的代码的时间复杂度是O(n*n).如何将其减少为O(n)或O(nlog(n))伪代码或算法的解释对我来说真的很有用这是问题陈述.问题陈述

如果连续数字之间的差异在正数和负数之间严格交替,则数字序列称为Z字形序列.第一个差异(如果存在)可以是正面的也可以是负面的.具有少于两个元素的序列通常是Z字形序列.

例如,1,7,4,9,2,5是Z字形序列,因为差异(6,-3,5,-7,3)交替为正和负.相比之下,1,4,7,2,5和1,7,4,5,5不是Z字形序列,第一个是因为它的前两个差异是正的,第二个是因为它的最后差异是零.

给定一系列整数序列,返回序列的最长子序列的长度,该序列是Z字形序列.通过从原始序列中删除一些元素(可能为零)来获得子序列,剩余的元素保持其原始顺序.

这是我的代码

#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

你可以使用贪婪的方法在O(n)中做到这一点.取第一个不重复的数字 - 这是你的之字形子序列的第一个数字.检查阵列中的下一个数字是否小于或大于第一个数字.

情况1:如果较小,检查下一个元素并继续前进,直到找到最小元素(即)之后的元素将大于前一个元素.这将是你的第二个元素.

情况2:如果更大,检查下一个元素并继续前进,直到找到最大元素(即)之后的元素将小于前一个元素.这将是你的第二个元素.

如果您使用Case 1查找第二个元素,请使用Case 2查找第三个元素,反之亦然.在这两种情况之间保持交替,直到原始序列中没有更多元素.由此产生的数字将形成最长的之字形子序列.

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

由此产生的后果:

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

因此,最长的之字形子序列的长度是7.

你可以参考sjelkjd的解决方案来实现这个想法.