java - 递归地找到java中数组中最长的递增序列

Question

例如这是数组 [1, 4, 9, 2, 6, 7, 3, 5, 8, 10]。 1,2,3,5,8,10 就是答案

那么我怎样才能用递归来解决这个问题。

感谢您的帮助。

public class 4b {

   public static int getLongetsLadder(int[] array){
   int i=0; 
   int[] result = recursive(array,i); 

   return 0; 
   }
   public static int[] recursive(int[] array, int i)
   {
   return null;
   }


   public static int[] recurse(int  i, int arr[])
   {
       int[] answer = new int[1];
       answer[0]= arr[i];

       return answer;

   }
}

Answer 1

Java实现如下:

public static Integer[] recurse(int i, int li, int arr[]) {

    if(i == arr.length)
        return new Integer[0];

    boolean choice = (li == -1) || arr[li] < arr[i];
    /* now you have choice to choose it or skip it */
    if(choice) {
        /* choose it */
        ArrayList<Integer> l = new ArrayList<Integer>();
        l.add(i);
        for(Integer v : recurse(i + 1, i, arr)) {
            l.add(v);
        }

        /* dont choose it */
        ArrayList<Integer> r = new ArrayList<Integer>();
        for(Integer v : recurse(i + 1, li, arr)) {
            r.add(v);
        }

        /* return largest */
        return l.size() > r.size() ? l.toArray(new Integer[0]) : r.toArray(new Integer[0]);
    }

    /* skip and proceed */
    return recurse(i + 1, li, arr);
}

应该这样称呼:

public static void main(String[] args) {
    findLargest(1, 4, 9, 2, 6, 7, 3, 5, 8, 10);
}
public static void findLargest(int ... vals) {
    Integer[] longest = recurse(0, -1, vals);
    for(Integer i : longest) {
        System.out.println(vals[i]);
    }
}

上述调用的结果是 1, 2, 3, 5, 8, 10