使用递归找到所有可能的最长递增子序列

Question

我尝试使用递归找到所有可能的最长递增子序列。当我试着输入数组{10,22,9,33,21,50,41,40,60,55}，它的工作输出功率为：

10 22 33 40 55/
10 22 33 41 55/
10 22 33 50 55/
10 22 33 40 60/
10 22 33 41 60/
10 22 33 50 60/

但当我输入数组{2,-3,4,90,-2,-1,-10,-9,-8}，我得到了一个输出：

-3 4 90/
-3 -2 -1/
-10 -9 -8/

在这种情况下，我没有得到2 4 90。在我的代码中，为了说明这种情况，应该更改哪些内容？

public class Main { 
    public static void main(String[] args) { 
     int arr[]={10,22,9,33,21,50,41,40,60,55}; 
     int lis[]=new int[arr.length]; 
     for(int i=0;i<arr.length;i++){ 
      lis[i]=1; 
     } 
     for(int i=1;i<arr.length;i++){ 
      for(int j=0;j<i;j++){ 
       if(arr[i]>arr[j]&&lis[i]<lis[j]+1){ 
        lis[i]=lis[j]+1; 
       } 
      } 
     } 
     int max=0; 
     for(int i=0;i<arr.length;i++){ 
      if(max<lis[i]) 
       max=lis[i]; 
     } 
     //**************Recursive Print LIS**************** 
     int rIndex=-1; 
     for(int i=arr.length-1;i>=0;i--){ 
      if(lis[i]==max){ 
       rIndex=i; 
       break; 
      } 
     } 
     int res[]=new int[max]; 
     printLISRecursive(arr,rIndex,lis,res,max,max); 
    } 

    private static void printLISRecursive(int[] arr, int maxIndex, int[] lis, int[] res, int i, int max) { 
     if(maxIndex<0)return; 
     if(max==1&&lis[maxIndex]==1&&i==1){ 
      res[i-1]=arr[maxIndex]; 
//   System.out.println("Using Print Recursion:"); 
      for(int j=0;j<res.length;j++){ 
       System.out.print(res[j]+" "); 
      } 
      System.out.println(); 
      return; 
     } 
     if(lis[maxIndex]==max){ 
      res[i-1]=arr[maxIndex]; 
      printLISRecursive(arr, maxIndex-1, lis, res, i-1, max-1); 
     } 
     printLISRecursive(arr, maxIndex-1, lis, res, i, max); 
    } 

} 

Answer 1

public static int lcsrec(String x, String y) { 

    // If one of the strings has one character, search for that character 
    // in the other string and return the appropriate answer. 
    if (x.length() == 1) 
     return find(x.charAt(0), y); 
    if (y.length() == 1) 
     return find(y.charAt(0), x); 

    // Solve the problem recursively. 

    // Corresponding beginning characters match. 
    if (x.charAt(0) == y.charAt(0)) 
     return 1+lcsrec(x.substring(1), y.substring(1)); 

    // Corresponding characters do not match. 
    else 
     return max(lcsrec(x,y.substring(1)), lcsrec(x.substring(1),y)); 

    } 

Answer 2

public static String lcs(String a, String b){ 
    int aLen = a.length(); 
    int bLen = b.length(); 
    if(aLen == 0 || bLen == 0){ 
     return ""; 
    }else if(a.charAt(aLen-1) == b.charAt(bLen-1)){ 
     return lcs(a.substring(0,aLen-1),b.substring(0,bLen-1)) 
      + a.charAt(aLen-1); 
    }else{ 
     String x = lcs(a, b.substring(0,bLen-1)); 
     String y = lcs(a.substring(0,aLen-1), b); 
     return (x.length() > y.length()) ? x : y; 
    } 
} 

Answer 3

按照你回溯的想法，我写了下面的代码。为简单起见，许多输入参数可以被消除。

public class LIS { 

    private static int[] count; 

    public int longestIncreaseSubsequence(int[] seq) { 
     int n = seq.length; 

     for (int i = 0; i < n; i++) { 
      count[i] = 1; 
     } 

     for (int i = 1; i < n; i++) { 
      int max = 0; 
      for (int j = i-1; j >= 0; j--) { 
       if (seq[j] < seq[i]) max = Math.max(max, count[j]); 
      } 
      count[i] = max + 1; 
     } 

     int max = Integer.MIN_VALUE; 
     for (int i = 0; i < count.length; i++) { 
      if (count[i] > max) max = count[i]; 
     } 

     return max; 
    } 

    public void printLIS(int[] a, int k, int[] count, int[] arr, int max) { 
     if (k == max) { 
      for (int i = max; i >= 1; i--) { 
       System.out.printf("%d ", arr[a[i]]); 
      } 
      System.out.println(); 
     } else { 
      k++; 

      int[] candidates = new int[arr.length]; 
      int ncandidate = 0; 

      for (int i = a[k-1]; i >= 0; i--) { 
       if (count[i] == max-k+1 && (arr[i] < arr[a[k-1]] || count[i] == max)) { 
        candidates[ncandidate] = i; 
        ncandidate++; 
       } 
      } 

      for (int i = 0; i < ncandidate; i++) { 
       a[k] = candidates[i]; 
       printLIS(a, k, count, arr, max); 
      } 
     } 
    } 

    public static void main(String[] args) { 
     int[] input = {2,-3,4,90,-2,-1,-10,-9,-8}; 
     LIS lis = new LIS(); 

     count = new int[input.length]; 

     int max = lis.longestIncreaseSubsequence(input); 

     int[] a = new int[max+1]; 
     a[0] = input.length-1; 

     lis.printLIS(a, 0, count, input, max); 
    } 
}