如何減少查找最長鋸齒序列的時間複雜度？

Question

我試圖解決頂級編碼器上的問題鋸齒形序列。我的代碼的時間複雜度是O（n * n）。我怎樣才能把它減少到O（n）或O（nlog（n）） 僞代碼或算法的解釋將對我很有幫助 這裏是問題陳述。 問題陳述

數字序列被稱爲鋸齒形序列，如果連續數字正與負之間交替的嚴格之間的差異。第一個差異（如果存在的話）可能是正面的或負面的。具有少於兩個元素的序列平凡是一個之字形序列。

例如，1,7,4,9,2,5是鋸齒形序列，因爲差異（6，-3,5，-7,3）交替爲正值和負值。相反，1,4,7,2,5和1,7,4,5,5不是之字形序列，第一個是因爲它的前兩個差值是正值，第二個是因爲它的最後差值是零。

給定一個整數序列序列，返回Zig-zag序列中最長的序列子序列的長度。通過從原始序列中刪除一些元素（可能爲零）來獲得子序列，其餘元素保持其原始順序。

這裏是我的代碼

#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）。在最壞的情況下，複雜度是O（2^n）。不過，我做了一些檢查，儘快切斷子樹。

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; 
} 

Answer 2

您可以使用RMQs刪除內部for-loop。當你發現了dp[i][0]和dp[i][1]答案，將其保存兩個RMQ樹 - 比如，RMQ 和RMQ - 就像你現在用dp陣列的兩行做的事情。因此，當您計算dp[i][0]時，您將值dp[i][0]放置在位置a[i]中的RMQ ，這意味着有一個長度爲dp[i][0]的Z字形序列越來越以編號a[i]結尾。

然後，爲了計算dp[i + 1][0]，您不必遍歷0和i之間的所有數字。相反，您可以在位置>a[i + 1]上查詢最大數量的RMQ 。這會給你最長的之字形子序列，結尾的數字大於當前數字 - 也就是最長的一個數字，可以繼續遞減，數字爲a[i + 1]。然後，您可以對另一半Z字形子序列執行RMQ 。

由於您可以實現查詢複雜度爲O(log N)的動態RMQ，因此總體複雜度爲O(N log N)。

Answer 3

U可以在O（n）使用貪婪的方法。取第一個不重複的數字 - 這是您的曲折子序列的第一個數字。檢查數組中的下一個數字是小於還是大於第一個數字。

案例1：如果較小，檢查下一個元素到和繼續下去，直到你找到的最小元素（IE）之後，這將是比以前更大的元素元素。這將是你的第二個元素。

案例2：如果更大，檢查下一個元素到和繼續下去，直到你找到的最大元素（IE）之後，這將是比以前的元素較少的元素。這將是你的第二個元素。

如果你已經使用案例1來查找第二個元素，請使用案例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的solution以實現此想法。

Answer 4

您可以在O(n)時間和O(n)多餘的空間解決這個問題。

算法如下。

1. 存儲替代項的大小n-1
2. 現在遍歷新的數組只是檢查替代長期的產品是否是小於零或沒有的新陣列的區別。
3. 相應地增加結果。如果在遍歷時發現該數組的產品大於零，那麼您將存儲結果並再次開始對差異數組中的其餘元素進行計數。
4. 找到它們之間的最大存儲到結果，並return (result+1)

下面是它的實現在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 5

這是一個純粹的理論解。如果你在學術環境中被要求，站在黑板旁邊，這就是你如何解決它的方法。

可以使用動態編程來產生上述問題的解決方案：

子問題有以下形式：如果我有一個元素x序列的，什麼是該元素的結束最長子？

然後你可以使用遞歸調用，它應該是這個樣子的工作你的解決方案（關係的方向可能是錯誤的，我沒有檢查它）：

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) 

這應該是O(n) （存儲Q（i）和P（i）的每個輸出），因爲每個子問題只計算一次：n*|P| + n*|Q|。

這些調用返回解決方案的長度 - 實際結果可以通過在找到最大值時存儲「父指針」來找到，然後在這些指針上向後遍歷。

可以避開遞歸簡單地通過替換函數與數組查找調用：P[i]和Q[i]，並使用for循環。