動態編程：使用只有一個dp數組找到最長的子序列zig zag

Question

這個問題只能使用一個dp數組完成嗎？ 這是Topcoder的曲折問題（http://community.topcoder.com/stat?c=problem_statement&pm=1259&rd=4493） 如果連續數字之間的差異在正數和負數之間嚴格交替，那麼數字序列稱爲Z字形序列。第一個差異（如果存在的話）可能是正面的或負面的。具有少於兩個元素的序列平凡是一個之字形序列。

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

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

Answer 1

僅供參考：帶兩個數組的DP使用數組A [1..n]其中A [i]是以元素i結尾爲zig的Z字形序列的最大長度，數組B [ 1..n]其中B [i]是在元素i上以zag結尾的之字形序列的最大長度。對於從1到n的i，此DP使用A數組的先前條目計算B [i]，並使用B數組的先前條目計算A [i]。以額外的循環爲代價，可以按需重新創建B條目，從而只使用A數組。不過，我不確定這是否能解決您的問題。

（同樣，由於輸入數組是如此短暫，有任何數量的編碼技巧不值一提的。）

Answer 2

下面是一個嘗試，我要回的，你有鋸齒形的指數。在你的第二個輸入（1,4,7,2,5）中，它返回5和4的索引，因爲它是從4,7,2,5起的鋸齒形。

您可以根據結果判斷整個數組是否爲鋸齒形。

public class LongestZigZag 
    { 
     private readonly int[] _input; 

     public LongestZigZag(int[] input) 
     { 
      _input = input; 
     } 

     public Tuple<int,int> Sequence() 
     { 
      var indices = new Tuple<int, int>(int.MinValue, int.MinValue); 

      if (_input.Length <= 2) return indices; 

      for (int i = 2; i < _input.Length; i++) 
      { 
       var firstDiff = _input[i - 1] - _input[i - 2]; 
       var secondDiff = _input[i] - _input[i - 1]; 

       if ((firstDiff > 0 && secondDiff < 0) || (firstDiff < 0 && secondDiff > 0)) 
       { 
        var index1 = indices.Item1; 
        if (index1 == int.MinValue) 
        { 
         index1 = i - 2; 
        } 

        indices = new Tuple<int, int>(index1, i); 
       } 
       else 
       { 
        indices = new Tuple<int, int>(int.MinValue, int.MinValue); 
       } 
      } 

      return indices; 
     } 
    } 

Answer 3

動態規劃需要O（N 2 ）時間來運行的程序。我設計了一個線性時間複雜度爲O（n）的代碼。一旦進入陣列，它會給出最大可能序列的長度。我已經針對這個問題測試了不同站點提供的很多測試用例，並且獲得了積極的結果。

這裏是我的C語言實現的代碼：

#include <stdio.h> 
#include <stdlib.h> 

int main() 
{ 
int i,j; 
int n; 
int count=0; 
int flag=0; 
scanf(" %d",&n); 
int *a; 
a = (int*)malloc(n*sizeof(a)); 

for(i=0;i<n;i++) 
{ 
    scanf(" %d",&a[i]); //1,7,5,10,13,15,10,5,16,8 
} 
i=0; 
if(a[0] < a[1]) 
{ 
    count++; 
    while(a[i] <= a[i+1] && i<n-1) 
    i++; 

    if(i==n-1 && a[i-1]<a[i]) 
    { 
     count++; 
     i++; 
    }  
} 
    while(i<n-1) 
    { count++; 
     while(a[i] >= a[i+1] && i<n-1) 
     { 
     i++; 
     } 
     if(i==n-1 && a[i-1]>a[i]) 
     { 
      count++; 
      break; 
     }  
     if(i<n-1) 
     count++; 
     while(a[i] <= a[i+1] && i<n-1) 
     { 
      i++; 
     } 
     if(i==n-1 && a[i-1]<a[i]) 
     { 
      count++; 
      break; 
     }   
    }  

printf("%d",count); 
return 0; 
}  

Answer 4

public class ZigZag 
{ 

    public void maxZigZag(int[] zigzag) 
    { 
    int sign[]=new int[zigzag.length]; 
    int p=0; 
    int max=1; 
     for(int j=0;j<zigzag.length-1;j++) 
     { 
      if(zigzag[j+1]-zigzag[j] > 0) 
       sign[p++]=1; 
      else if(zigzag[j+1]-zigzag[j] < 0) 
       sign[p++]=-1; 
     } 
     /*for(int s:sign) 
     { 
      System.out.print(s+","); 
     }*/ 
     System.out.println(); 
     for(int k=0;k<p;k++) 
     { 
      if(sign[k]==sign[k+1]) 
      { 
       sign[k]=0; 

      } 
     } 
     /*for(int s:sign) 
     { 
      System.out.print(s+","); 
     }*/ 
     System.out.println(); 
     for(int s=0;s<p;s++) 
     { 
      if(sign[s]!=0) 
      { 
       max++; 
       /*System.out.print(sign[s]+",");*/ 
      } 

     } 

     System.out.println("max length zigzag:"+max); 
    } 

    public static void main(String args[]) 
    { 
    ZigZag z=new ZigZag(); 
    int zigzag[]={374, 40, 854, 203, 203, 156, 362, 279, 812, 955, 
      600, 947, 978, 46, 100, 953, 670, 862, 568, 188, 
      67, 669, 810, 704, 52, 861, 49, 640, 370, 908, 
      477, 245, 413, 109, 659, 401, 483, 308, 609, 120, 
      249, 22, 176, 279, 23, 22, 617, 462, 459, 244}; 
    z.maxZigZag(zigzag); 
    } 
} 

Answer 5

每一個（我的話題的知識，所以不要想當然），你用動態規劃制定出解決方案，來直到代表「解決方案空間」（意思是每個可能的解決方案都是正確的，不一定是最優的）與定向非循環圖（Directed Acyclic Graph）。

例如，如果你正在尋找一個最長上升 subseqence，那麼解決的空間可以表示爲下面的DAG：

• 節點都標有序列
• 邊緣的數量兩個節點之間e(u, v)表示valueOf(u) < valueOf(v)（其中valueOf(x)是與節點x相關聯的值）

在動態編程，找到問題的最佳解決方案與以正確的方式遍歷此圖形是一回事。由該圖提供的信息在某種意義上由該DP陣列表示。

在這種情況下，我們有兩個訂購操作。如果我們將這兩個圖表顯示在其中一個圖表上，那麼該圖表不會是非循環的 - 我們將需要至少兩個圖表（一個表示<關係，另一個表示>）。

如果拓撲排序需要兩個DAG，解決方案將需要兩個DP數組，或者一些巧妙的方式來指示DAG中的哪條邊對應於哪個排序操作（在我看來，這無疑會使問題複雜化）。

因此不，你不能只用一個DP陣列。你至少需要兩個。至少如果你想要一個純粹通過使用動態編程的簡單解決方案。

---

的遞歸調用這個問題應該是這個樣子（關係的方向可能是錯誤的，我沒有檢查它）：

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) + 1 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) + 1 if A[i] > A[j] for every 0 <= j < i) 

這應該是O（N）與正確的memoization（兩個DP陣列）。這些調用返回解決方案的長度 - 每當找到最大值時，通過存儲「父指針」可找到實際結果，然後在這些指針上向後遍歷。