最長遞增子序列遞歸版本

Question

傳統最長遞增子序列問題。 這是遞歸版本（不是DP版本） 我意識到version1代碼有一個bug，所以我將它改爲version2。

我不清楚明白爲什麼版本2的作品和VERSION1具有輸入A0

錯誤，請參見下面的版本1和版本2：

static int lis1(int[] v) { 
    int maxLen = 1; 

    for(int i = 1; i < v.length; i++) { 
     List<Integer> w = new ArrayList<Integer>();  

     for(int j = 0; j < i; j++) { 
      if(v[j] < v[i]) { 
       w.add(v[j]);     
      } 
     } 

     // it used to be the following one line which has bug for input A0 
     //cand = lis1(l2a(w)) + 1;   // version1 

     // so I changed it to the following, but can't clearly understand why it works. 
     // without this part, it has but for input A0 
     int cand = 1;       // version2 
     if(v[i-1] < v[i]) 
      cand = lis1(l2a(w)) + 1; 
     else 
      cand = lis1(l2a(w)); 

     maxLen = Math.max(maxLen, cand);   
    } 

    return maxLen;  
} 

public static void main(String[] args) { 
    int[] A0 = {3, 2, 5, 6}; // for this input version1 had a bug which printed out 4 (instead of 3) 
    int[] A1 = {1, 2, 3, 3, 2, 4, 6, 7};       // 6 
    int[] A2 = { 10, 22, 9, 33, 21, 50, 41, 60, 80 };    // 6 
    int[] A3 = { 5, 0, 4, 2, 3, 7, 1 };        // 4 
    int[] A4 = { 2, 7, 3, 4, 9, 8, 12 };       // 5 
    int[] A5 = {3, 4, 2, 5 };          // 3 

Answer 1

其實......既不是你的版本的作品。嘗試把A0={3,2,7,6}，你的V2返回2，顯然是錯誤的。

至於v1，對於v={3,2}答案應該是1，對嗎？讓我們來看看你的代碼的作用。當索引i=1，w內部for循環後等於{}。然後你做了遞歸調用w={}，它應該已經返回0，但它返回1.爲什麼，因爲你的maxlen變量，它被錯誤地初始化爲1。此錯誤傳播到整個{3,2,5,6}並給出錯誤答案。

因爲你if條件，那麼失敗(3<2)，並返回先前所返回1.

只要刪除整個版本2，正確maxlen初始化v2的意外解決了這個問題。然後用i=0開始外部循環for(int i = 1; i < v.length; i++)，否則單個元素數組將得到0。

static int lis1(int[] v) { 
int maxLen = 0; 

for(int i = 0; i < v.length; i++) { 
    List<Integer> w = new ArrayList<Integer>();  

    for(int j = 0; j < i; j++) { 
     if(v[j] < v[i]) { 
      w.add(v[j]);     
     } 
    }  
    cand = lis1(l2a(w)) + 1;   // version1 

    maxLen = Math.max(maxLen, cand);   
} 

return maxLen;  
}