最長増加サブシーケンス再帰バージョン

Question

従来の最長増加サブシーケンス問題。 これは再帰版（DP版ではない）です 私はバージョン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

が実際に...あなたのバージョンのどちらも動作します：

は、私ははっきりとバージョン2作品とバージョン1は、以下のバージョン1とバージョン2を参照してください入力A0

のためのバグを持っている理由を理解していません。 A0={3,2,7,6}を入れてみてください。あなたのv2は明らかに間違って2を返します。

v1については、v={3,2}の回答は1である必要がありますか？あなたのコードが何をしているか見てみましょう。インデックスi=1の場合、内部forの後のwループは{}になります。その後、w={}への再帰呼び出しを行いましたが、これは0を返すはずですが、1を返します。maxlen変数のために、間違って1で初期化されます。このエラーは{3,2,5,6}全体に伝播し、間違った答えを返します。あなたのif状態が続い(3<2)失敗し、それが以前にちょうど全体のバージョン2、正しいmaxlen初期設定を削除

1を返さ返すため、誤ってこの問題を解決V2

。そして外側ループfor(int i = 1; i < v.length; i++)をi=0で開始します。そうしないと、1要素配列に対して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;  
}