トップコーダーの問題ジグザグシーケンスを解決しようとしていました.私のコードの時間の複雑さはO(n * n)です。どうすれば O(n) または O(nlog (n)) に減らすことができますか? 疑似コードまたはアルゴリズムの説明は、私にとって非常に役立ちます。問題のステートメントは次のとおりです。問題文
連続する数の差が正と負の間で厳密に交互になる場合、数列はジグザグ数列と呼ばれます。最初の差異 (存在する場合) は、正または負のいずれかです。要素が 2 つ未満のシーケンスは、自明にジグザグ シーケンスです。
たとえば、1,7,4,9,2,5 は、差 (6,-3,5,-7,3) が交互に正と負になるため、ジグザグ シーケンスです。対照的に、1,4,7,2,5 と 1,7,4,5,5 はジグザグ シーケンスではありません。1 つ目は最初の 2 つの差が正であるため、2 つ目は最後の差がゼロであるためです。
整数のシーケンス sequence を指定すると、ジグザグ シーケンスであるシーケンスの最長のサブシーケンスの長さを返します。サブシーケンスは、元のシーケンスからいくつかの要素 (おそらくゼロ) を削除し、残りの要素を元の順序のままにすることによって取得されます。
そして、ここに私のコードがあります
#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]);
}
};