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

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

主.java

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

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