以递归方式在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

Answer 2

这里是一个工作准备运行的例子。 这是基于这样的想法，即在每一步中，您都可以尝试在搜索中增加序列（只有当它通过实际大于最后一个项目的条件时）或排除（忽略）当前项目不在序列中。 这样你就可以获得递归来覆盖所有可用的路径。

IntList.java

public class IntList { 
    private IntNode _head; 

    public IntList() { 
     _head = null; 
    } 

    public IntList(IntNode node) { 
     _head = node; 
    } 

    public int longest() { 
     return longest2(_head,0); 
    } 

    public int longest(IntNode current,int max) { 
     if (current.getNext() == null) 
     { 
      if (current.getValue() > max) 
       return 1; 

      return 0; 
     } 

     int with, without; 

     without = longest2(current.getNext(),max); 

     if (current.getValue() > max) { 
      with = 1 + longest2(current.getNext(), current.getValue()); 
      return Math.max(with,without); 
     } 

     return without; 
    } 
} 

IntNode.java

public class IntNode { 
    private int _value; 
    private IntNode _next; 

    public IntNode(int val, IntNode n) { 
     _value = val; 
     _next = n; 
    } 

    public int getValue()  { 
     return _value; 
    } 

    public IntNode getNext() { 
     return _next; 
    } 
    public void setValue(int v) { 
     _value = v; 
    } 
    public void setNext(IntNode node) { 
     _next = node; 
    } 
} 

Main.java

公共类主要{ 公共静态无效主要（字符串[] args）{

 IntNode n1 = new IntNode(3, null); 
     IntNode n2 = new IntNode(5, n1); 
     IntNode n3 = new IntNode(10, n2); 
     IntNode n4 = new IntNode(5, n3); 
     IntNode n5 = new IntNode(1, n4); 
     IntNode n6 = new IntNode(4, n5); 
     IntNode n7 = new IntNode(2, n6); 
     IntList list = new IntList(n7); 
     System.out.println("should be 4, is: " + list.longest()); 


     IntNode n11 = new IntNode(7, null); 
     IntNode n21 = new IntNode(6, n11); 
     IntNode n31 = new IntNode(5, n21); 
     IntNode n41 = new IntNode(4, n31); 
     IntNode n51 = new IntNode(3, n41); 
     IntNode n61 = new IntNode(2, n51); 
     IntNode n71 = new IntNode(1, n61); 
     IntList list2 = new IntList(n71); 
     System.out.println("should be 7, is: " + list2.longest()); 

     IntNode n12 = new IntNode(10, null); 
     IntNode n22 = new IntNode(5, n12); 
     IntNode n32 = new IntNode(5, n22); 
     IntNode n42 = new IntNode(1, n32); 
     IntNode n52 = new IntNode(1, n42); 
     IntNode n62 = new IntNode(4, n52); 
     IntNode n72 = new IntNode(2, n62); 
     IntList list3 = new IntList(n72); 
     System.out.println("should be 4, is: " +list3.longest()); 

     IntNode n13 = new IntNode(7, null); 
     IntNode n23 = new IntNode(4, n13); 
     IntNode n33 = new IntNode(3, n23); 
     IntNode n43 = new IntNode(1, n33); 
     IntNode n53 = new IntNode(8, n43); 
     IntNode n63 = new IntNode(5, n53); 
     IntNode n73 = new IntNode(1, n63); 
     IntList list4 = new IntList(n73); 
     System.out.println("should be 4, is: " + list4.longest()); 
    } 
}