Algorithm for Longest Increasing Subsequence timing out

Question

I am solving the Longest Subsequence problem at HackerRank. I am using Dynamic Programming algorithm to solve the Longest subsequence problem. The time complexity for my algorithm is O(n^2). Although my solution presents the correct result, its timimg out for most of the test cases. I am not able to improve my algorithm, so that it calculates the result faster. Let me know in case anybody can suggest anything. My function is as follows:

static ArrayList<Integer> calcSolution(int[] arr) throws Exception{
        ArrayList<ArrayList<Integer>> prev = new ArrayList<ArrayList<Integer>>(); 
        ArrayList<Integer> lis = new ArrayList<Integer>();

        lis.add(arr[0]);
        prev.add(lis);
        for(int i=1 ; i<arr.length ; i++){
            prev.add(new ArrayList<Integer>());
            for(int j=0 ; j<i ; j++){
                if( (arr[i] > arr[j]) && (prev.get(i).size() < (prev.get(j).size()+1)) ){
                    prev.get(i).addAll(prev.get(j));
                }
            }
            prev.get(i).add(new Integer(arr[i]));
        }

        for(int i=0 ; i<prev.size() ; i++){
            for(int j=0 ; j<prev.get(i).size(); j++){
                System.out.print(prev.get(i).get(j));
            }
            System.out.println();
        }

        lis = prev.get(0);
        for(int i=1 ; i<prev.size() ; i++){
            if(prev.get(i).size() > lis.size()){
                lis = prev.get(i);
            }
        }

        return lis;
    }

My question is: - Is there anything that I can do to this algorithm that can make it faster. The algorithm suggested in the other post is a completely different algorithm.

@Anonymous: I see, I was thinking of the longest common substring problem. — Micromega, Apr 05 '15 at 08:07

score 0 · Answer 1 · answered Apr 06 '15 at 17:01

Your implementation has time complexity O(n^3) and not O(n^2).

prev.get(i).addAll(prev.get(j));

is unnecessary and expensive.

For every element, you need to remember the previous link and the length of the subsequence ending at it. You don't need to memorize the actual subsequence at each element.

Algorithm for Longest Increasing Subsequence timing out

1 Answers1