potential O(n) solution to Longest Increasing Subsequence

Question

I was trying to answer this problem, using just recursion (Dynamic programming) http://en.wikipedia.org/wiki/Longest_increasing_subsequence

From the article, and around SO, I realise the most efficient existing solution is O(nlgn). My solution is O(N), and I cannot find a case that it fails. I include unit test cases that I used.

import static org.junit.Assert.assertEquals;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

import org.junit.Test;

public class LongestIncreasingSubseq {

    public static void main(String[] args) {
        int[] arr = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, 1};
        getLongestSubSeq(arr);
    }

    public static List<Integer> getLongestSubSeq(int[] arr) {
        List<Integer> indices = longestRecursive(arr, 0, arr.length-1);
        List<Integer> result = new ArrayList<>();
        for (Integer i : indices) {
            result.add(arr[i]);
        }

        System.out.println(result.toString());
        return result;
    }

    private static List<Integer> longestRecursive(int[] arr, int start, int end) {
        if (start == end) {
            List<Integer> singleton = new ArrayList<>();
            singleton.add(start);
            return singleton;
        }

        List<Integer> bestRightSubsequence = longestRecursive(arr, start+1, end); //recursive call down the array to the next start index
        if (bestRightSubsequence.size() == 1 && arr[start] > arr[bestRightSubsequence.get(0)]) {
            bestRightSubsequence.set(0, start); //larger end allows more possibilities ahead
        } else if (arr[start] < arr[bestRightSubsequence.get(0)]) {
            bestRightSubsequence.add(0, start); //add to head
        } else if (bestRightSubsequence.size() > 1 && arr[start] < arr[bestRightSubsequence.get(1)]) {
            //larger than head, but still smaller than 2nd, so replace to allow more possibilities ahead
            bestRightSubsequence.set(0, start); 
        }

        return bestRightSubsequence;
    }

    @Test
    public void test() {
        int[] arr1 = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, 1};
        int[] arr2 = {7, 0, 9, 2, 8, 4, 1};
        int[] arr3 = {9, 11, 2, 13, 7, 15};
        int[] arr4 = {10, 22, 9, 33, 21, 50, 41, 60, 80};
        int[] arr5 = {1, 2, 9, 4, 7, 3, 11, 8, 14, 6};
        assertEquals(getLongestSubSeq(arr1), Arrays.asList(0, 4, 6, 9, 11, 15));
        assertEquals(getLongestSubSeq(arr2), Arrays.asList(0, 2, 8));
        assertEquals(getLongestSubSeq(arr3), Arrays.asList(9, 11, 13, 15));
        assertEquals(getLongestSubSeq(arr4), Arrays.asList(10, 22, 33, 50, 60, 80));
        assertEquals(getLongestSubSeq(arr5), Arrays.asList(1, 2, 4, 7, 11, 14));
    }

}

The cost is strictly O(n) because of the relation T(n) = T(n-1) + O(1) => T(n) = O(n)

Can anyone find a case where this fails, or any bugs there are? Many thanks.

UPDATE: Thanks everyone for pointing out my mistake in previous implementation. Final code below passes all test cases that it used to fail.

The idea is to list (compute) all possible increasing subsequences (each starts from index i from 0 to N.length-1) and pick the longest subsequence. I use memoization (using a hash table) to avoid recomputation of already computed subsequences - so for each starting index we only compute all increasing subsequences once.

However, I am not certain of how to formally derive time complexity in this case - I would be grateful if anyone can shed light on this. Many thanks.

import static org.junit.Assert.assertEquals;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import org.junit.Test;

public class LongestIncreasingSubsequence {

    public static List<Integer> getLongestSubSeq(int[] arr) {
        List<Integer> longest = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            List<Integer> candidate = longestSubseqStartsWith(arr, i);
            if (longest.size() < candidate.size()) {
                longest = candidate;
            }
        }

        List<Integer> result = new ArrayList<>();
        for (Integer i : longest) {
            result.add(arr[i]);
        }

        System.out.println(result.toString());
        cache = new HashMap<>(); //new cache otherwise collision in next use - because object is static
        return result;
    }

    private static Map<Integer, List<Integer>> cache = new HashMap<>();
    private static List<Integer> longestSubseqStartsWith(int[] arr, int startIndex) {
        if (cache.containsKey(startIndex)) { //check if already computed
            //must always return a clone otherwise object sharing messes things up
            return new ArrayList<>(cache.get(startIndex)); 
        }

        if (startIndex == arr.length-1) {
            List<Integer> singleton = new ArrayList<>();
            singleton.add(startIndex);
            return singleton;
        }

        List<Integer> longest = new ArrayList<>();
        for (int i = startIndex + 1; i < arr.length; i++) {
            if (arr[startIndex] < arr[i]) {
                List<Integer> longestOnRight = longestSubseqStartsWith(arr, i);
                if (longestOnRight.size() > longest.size()) {
                    longest = longestOnRight;
                }
            }
        }

        longest.add(0, startIndex);
        List<Integer> cloneOfLongest = new ArrayList<>(longest);
        //must always cache a clone otherwise object sharing messes things up
        cache.put(startIndex, cloneOfLongest); //remember this subsequence
        return longest;
    }

    @Test
    public void test() {
        int[] arr1 = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15, 1};
        int[] arr2 = {7, 0, 9, 2, 8, 4, 1};
        int[] arr3 = {9, 11, 2, 13, 7, 15};
        int[] arr4 = {10, 22, 9, 33, 21, 50, 41, 60, 80};
        int[] arr5 = {1, 2, 9, 4, 7, 3, 11, 8, 14, 6};
        int[] arr6 = {0,0,0,0,0,0,1,1,1,1,2,3,0,0,0,1,1,0,1,1,0,1,0,3};
        int[] arr7 = {0,1,2,0,1,3};
        int[] arr8 = {0,1,2,3,4,5,1,3,8};
        assertEquals(getLongestSubSeq(arr1), Arrays.asList(0, 4, 6, 9, 13, 15));
        assertEquals(getLongestSubSeq(arr2), Arrays.asList(0, 2, 8));
        assertEquals(getLongestSubSeq(arr3), Arrays.asList(9, 11, 13, 15));
        assertEquals(getLongestSubSeq(arr4), Arrays.asList(10, 22, 33, 50, 60, 80));
        assertEquals(getLongestSubSeq(arr5), Arrays.asList(1, 2, 4, 7, 11, 14));
        assertEquals(getLongestSubSeq(arr6), Arrays.asList(0,1,2,3));
        assertEquals(getLongestSubSeq(arr7), Arrays.asList(0,1,2,3));
        assertEquals(getLongestSubSeq(arr8), Arrays.asList(0, 1, 2, 3, 4, 5, 8));
    }

    public static void main(String[] args) {
        int[] arr1 = {7, 0, 9, 2, 8, 4, 1};
        System.out.println(getLongestSubSeq(arr1));
    }

}

Answer 1

Your program fails in this test case

int[] arr5 = {0,0,0,0,0,0,1,1,1,1,2,3,0,0,0,1,1,0,1,1,0,1,0,3};

Your result [0, 1, 3] Shouldn't it be [0,1,2,3]

Answer 2

Just now I tried your algorithm by using following test case:

 @Test
    public void test() {

      int[] arr1 = {0,1,2,3,4,5,1,3,8};
      assertEquals(getLongestSubSeq(arr1), Arrays.asList(0, 1, 2, 3, 4, 5, 8));
    }

and it's failed as it gives output {1, 3, 8} EDITED as per your comment.

Answer 3

Sorry to be the bearer of bad news, but this is actually O(n²). I'm not sure if you had something more formal in mind, but here is my analysis:

consider the case when the input is sorted in descending order
  (longestRecursive is never executed recursively, and the cache has no effect)

getLongestSubSeq iterates over the entire input -> 1:n
  each iteration calls longestRecursive
  longestRecursive compares arr[startIndex] < arr[i] for startIndex+1:n -> i - 1

Thus, the comparison arr[startIndex] < arr[i] occurs exactly sum(i - 1, 1, n) = n * (n - 1) / 2 times, which is certainly O(n²). You can force maximum cache usage by sending an input that is sorted ascending. In this case, getLongestSubSeq would call longestRecursive n times; the first of these would trigger n - 1 recursive calls, each of which would cause a cache miss and run i - 1 comparisons arr[startIndex] < arr[i] because nothing is put into the cache until the recursion starts unwinding. The number of comparisons is exactly the same as in the example where we bypassed the cache. In fact, the number of comparisons is always the same; introducing inversions in the input merely causes the code to trade recursions for iteration.

Answer 4

This is a O(n^2) Algorithm. Because there are two loops. The second loop is hidden inside a method call.

This is the first loop: for (int i = 0; i < arr.length; i++) . Inside this loop you called longestSubseqStartsWith(arr, i); . Look at longestSubseqStartWith implementation we see for (int i = startIndex + 1; i < arr.length; i++)

Answer 5

This is my Potential O(N) solution in python3.x :

l = list(map(int,input().split()))
t = []
t2 = []
m = 0
for i in l:
    if(len(t)!=0):
        if(t[-1]<=i):
            if(t[-1]!=1):
                 t.append(i)
        else:
            if(len(t)>m):
                t2 = t
                m = len(t)
            t = [i]
    else:
        t.append(i)
print(t2,len(t2))