рекурсивно обнаруживают самую длинную возрастающую последовательность в массиве в 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); 
} 

Thats, как она должна называться:

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

общественного класса Main { государственной статической силы основных (String [] 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()); 
    } 
}