最长递增子序列递归版本

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