Recursively finds the longest growing sequence in the array in java

综合编程 2018-01-10 阅读原文

for example this is array [1, 4, 9, 2, 6, 7, 3, 5, 8, 10]. and 1,2,3,5,8,10 is the answer

so how can i solve this with recursion.

thanks for any help.

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;

   }
}

Implement ion in Java is given below:

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 l = new ArrayList();
        l.add(i);
        for(Integer v : recurse(i + 1, i, arr)) {
            l.add(v);
        }

        /* dont choose it */
        ArrayList r = new ArrayList();
        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 how it should be called:

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

Result of above call was 1, 2, 3, 5, 8, 10

Hello, buddy!

责编内容by:Hello, buddy!阅读原文】。感谢您的支持!

您可能感兴趣的

CountDownLatch 简单举例 1 import java.util.Random; 2 import java.util.concurrent.CountDownLatch; 3 4 import org.slf4j.Logger; 5 ...
The same input list has two different queries in s... I want to establish single connection with sql server for two different queries having same input. Is that acheivable? Here is my code which will esta...
Loom prototype publicly available Ron Pressler ron.pressler at oracle.com Fri Jul 27 17:51:27 UTC 2018 Previous message: hg: loom/loom: 3 new changesets ...
月薪8k 和 月薪28K的程序员差距在哪里?... 回想自己做开发的这八年多,我获得了很多,技术能力、培训、出国、大公司的,还记得刚刚出来第一年那段时间,太多东西不懂的,我都是一切听从老大的安排,敲敲代码,看看数据库,测试自己和别人的代码;这样干了一年 第二年的时候我就在想,自己还要这样吗? 当然是否定的,不可能的,一年的经验自己完全可以入行...
.NetCore实践篇:使用zipkin4net推送数据到分布式监控zipkin(2)... 前言 《牧神记》有一句话说的好,破心中神。当不再对分布式,微服务,CLR畏惧迷茫的时候,你就破了心中神。 zipkin复习 第一篇: .Net架构篇:思考如何设计一款实用的分布式监控系统? 第二篇: NetCore实践篇:分布式监控客户端ZipkinTracer从入门到放弃...