Returning all the LIS of given array of int

Question

I have this assignment where I'm supposed to code an algorithm for finding the quantity of Longest Increasing Subsequences from an array of (different) integers and print them all.

I developed one which always gives me the right answer, but I have 2 issues with it:

1. It's a little slow

2. When the given array is between 150-200 integers long, it crashes with:

   OutOfMemory: heap space

I understand why it's a little slow, and to tell you the truth, it's not that slow when you think of Brute Force Algorithm alternatives.

And also, I'd like to be able to return the quantity of LISs independently from searching them (like finding the number of cheapest paths in a graph without returning them all), but I just can't seem to find a solution without counting them after finding them.

A little explanation:

The algorithm creates an (n+1)*(n+1) matrix (n = length of given array), rows representing given array, columns representing given array after sorting (ascending), fills the first row and the first column with 0s and then loops over it using different conditions to either:

• add an integer to the array(s) existing at given slot in this matrix (mat[i, j])
• copies all the existing arrays of the slot above and the slot aside (mat[i-1, j], mat[i, j-1]) into the current slot (without duplicates)
• copies the array(s) from the slot (above or aside) in which they are longer into current slot)
• just fills it with "nothing"

n.b.: I'm not actually creating a (n+1)*(n+1) matrix. Instead I create a 2*(n+1) matrix in which I only keep the last row calculated and the one I'm about to, then switch.

My problem might also come from my testing. I just can't seem to see it.

import java.util.Arrays;
import java.util.ArrayList;

public class LIS {
    private int[] arr;
    
    public LIS(int[] arr) {
        this.arr = new int[arr.length];
        System.arraycopy(arr, 0, this.arr, 0, arr.length);
    }
    
    public static int BSBinArray(int[] arr, int end, int value) {...}// BinarySearch
    public static void mergeSort(int [] arr, int low, int high){...}// 1st part of MergeSort
    public static int[] mergeSort(int [] arr){...}// 2nd part of MergeSort
    
    public int LISLength() {// get exclusively the length of the LIS(s)
        int[] help = new int[arr.length];
        help[0] = arr[0];
        int end = 0;
        
        for (int i = 0; i < arr.length; i++) {
            int index = BSBinArray(help, end, arr[i]);
            help[index] = arr[i];
            if(index > end) end++;
        }
        return end+1;
    }
    
    // returns a Node (class below) with all the info in it
    private Node buildMatrix() {
        int maxLength = LISLength();
        int[] sortArr = mergeSort(arr);
        
        Node[][] mat = new Node[2][arr.length + 1];
        for (int i = 0; i < mat.length; i++) {
            mat[i][0] = new Node(maxLength);
        }
        for (int i = 0; i < mat[0].length; i++) {
            mat[0][i] = new Node(maxLength);
        }
        
        int cur = 0;
        int prev = 0;
        for (int i = 1; i < arr.length+1; i++) {
            cur = (cur + 1)%2;
            prev = 1-cur;
            for (int j = 1; j < mat[0].length; j++) {
                if(arr[i-1] == sortArr[j-1]) {
                    mat[cur][j] = new Node(mat[prev][j-1]);
                    for (int k = 0; k < mat[cur][j].list.size(); k++) {
                        mat[cur][j].list.get(k)[mat[cur][j].localLength] = arr[i-1];
                    }
                    mat[cur][j].localLength++;
                }
                else {
                    if(mat[prev][j].localLength == mat[cur][j-1].localLength) {
                        if(mat[prev][j].localLength != 0) {
                            mat[cur][j] = new Node(mat[prev][j]);
                            
                            for (int k = 0; k < mat[cur][j-1].list.size(); k++) {
                                boolean contains = false;
                                for (int k2 = 0; k2 < mat[prev][j].list.size() && !contains; k2++) {
                                    contains = Arrays.equals(mat[cur][j-1].list.get(k), mat[prev][j].list.get(k2));
                                }
                                if(!contains) mat[cur][j].list.add(mat[cur][j-1].list.get(k));
                            }
                        }
                        else {
                            mat[cur][j] = new Node(maxLength);
                        }
                    }
                    else if(mat[prev][j].localLength > mat[cur][j-1].localLength) {
                        mat[cur][j] = new Node(mat[prev][j]);
                    }
                    else {
                        mat[cur][j] = new Node(mat[cur][j-1]);
                    }
                }
            }
        }
        return mat[cur][mat[0].length-1];
    }
    public void printLengthLIS() {
        int length = LISLength();
        System.out.println("LISs are " + length + " integers long.");
    }
    public void printNumOfLIS() {
        int numOfLIS = buildMatrix().list.size();
        System.out.println("There are " + numOfLIS + " LISs.");
    }
    public void printAllLIS() {
        ArrayList<int[]> info = buildMatrix().list;
        
        System.out.println("All the LISs are: ");
        for (int i = 0; i < info.size(); i++) {
            System.out.println(Arrays.toString(info.get(i)));
        }
    }
    
    private class Node {
        int localLength;
        ArrayList<int[]> list;
        
        public Node(int x) {
            localLength = 0;
            list = new ArrayList<int[]>();
            list.add(new int[x]);
            
        }
        public Node(Node n) {
            localLength = n.localLength;
            list = new ArrayList<int[]>();
            for(int[] temp : n.list) {
                list.add(temp.clone());
            }
        }
    }

And here is my testing code (with a lot of monitoring info):

for(int i = 10; i < 1000; i++) {
        
    System.out.println("available memory BEFORE: " + java.lang.Runtime.getRuntime().maxMemory());
    
    // creates a random array of different integers
    Set<Integer> set = new HashSet<Integer>();
    int temp = i;
    while(temp != 0) {
        if(set.add((int)(Math.random()*1000))) temp--;
    }
    int[] arr = new int[set.size()];
    Iterator<Integer> it = set.iterator();
    
    // into an actual array
    for (int j = 0; j < arr.length; j++) {
        arr[j] = it.next();
    }
    set = null;// supposed to free this memory allocation for the GC
        
    System.out.println("i="+i+", length="+arr.length);
    System.out.println(Arrays.toString(arr));
        
    LIS test = new LIS(arr, arr.length+1);
        
    test.printLengthLIS();
    
    long startTime = System.currentTimeMillis();
    test.printNumOfLIS();
    long endTime = System.currentTimeMillis();
    long totalTime = endTime - startTime;
    System.out.println("It took me " + totalTime + " ms.");
    
    test.printAllLIS();
        
    test = null;
    System.out.println("available memory AFTER: " + java.lang.Runtime.getRuntime().freeMemory());
}

Answer 1

Taking the changed/alternate specification in to consideration, you are allowed to 'skip' values to get the increasing sequences.

The right algorithm for this problem is to use recursion. Now, because you are skipping things, there are a lot of potential combinations of 'winning' sequences.... as a result, you cannot safely store them all in memory. The right solution to that problem is to use an iterator.

Here is your problem worked out with a relatively small memory footprint, and an iterator used to report the actual sequences.....

There is room for optimization still in the recursion, and, it may be worth adopting the iterative approach of the iterator instead of the recursion.... your call. Having both examples will give you something to think about.

import java.util.Arrays;
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Random;

public class SkippingLIS implements Iterable<int[]> {

    private static final class MutableInt {
        int value = 0;
    }

    private final int[] data;
    private final int sequencecount;
    private final int longest;

    public SkippingLIS(int[] arr) {

        data = Arrays.copyOf(arr, arr.length);

        int[] stack = new int[data.length];
        MutableInt counter = new MutableInt();

        longest = recurseCount(data, 0, stack, 0, 0, counter);

        sequencecount = counter.value;
    }

    private class MyIterator implements Iterator<int[]> {

        int[] cursor = new int[1 + longest * 2];
        int[] stack = new int[1 + longest * 2];
        int count = 0;
        int depth = 0;

        public MyIterator() {
            cursor[0] = -1;
        }

        @Override
        public boolean hasNext() {
            return count < sequencecount;
        }
        @Override
        public int[] next() {
            if (!hasNext()) {
                throw new NoSuchElementException();
            }

            do {
                cursor[depth]++;
                while (cursor[depth] >= data.length) {
                    depth--;
                    cursor[depth]++;
                }
                if (depth > 0) {
                    while (cursor[depth] < data.length && data[cursor[depth]] <= stack[depth - 1]) {
                        cursor[depth]++;
                    }
                }
                if (cursor[depth] < data.length) {
                    stack[depth] = data[cursor[depth]];
                    if (depth < longest) {
                        depth++;
                        cursor[depth] = cursor[depth - 1];
                    }
                }
            } while (cursor[depth] >= data.length || depth != longest);
            count++;
            return Arrays.copyOf(stack, longest);
        }
        @Override
        public void remove() {
            throw new UnsupportedOperationException();

        }

    }

    @Override
    public Iterator<int[]> iterator() {
        return new MyIterator();
    }


    private static int recurseCount(final int[] arr, final int cursor, final int[] stack, final int length, final int maxlen,
            final MutableInt results) {
        if (cursor >= arr.length) {
            // max length so far....
            return length;
        }
        int loopmax = maxlen;
        if (length > loopmax) {
            results.value = 0;
            loopmax = length;
        }
        if (loopmax == length) {
            results.value++;
        }
        for (int i = arr.length - 1 - loopmax + length; i >= cursor; i--) {
            if (length == 0 || arr[i] > stack[length - 1]) {
                stack[length] = arr[i];
                int nmax = recurseCount(arr, i, stack, length + 1, loopmax, results);
                if (nmax > loopmax) {
                    loopmax = nmax;
                }
            }
        }
        return loopmax;

    }

    public int longestLength() {// get exclusively the length of the LIS(s)
        return longest;
    }

    public void printLengthLIS() {
        System.out.println("LISs are " + longest + " integers long.");
    }
    public void printNumOfLIS() {
        System.out.println("There are " + sequencecount + " LISs.");
    }
    public void printAllLIS(int limit) {
        if (sequencecount < limit) {
            limit = sequencecount;
        }
        System.out.println("First " + limit + " of " + sequencecount + " of the LISs are: ");
        int cnt = 0;
        for (int[] sp : this) {
            cnt++;
            System.out.println(Arrays.toString(sp));
            if (cnt >= limit) {
                return;
            }
        }
    }

    private static final void testSize(int size, Random rand) {
        //System.out.println("available memory BEFORE: " + java.lang.Runtime.getRuntime().maxMemory());

        // creates a random array of different integers
        int[] arr = new int[size];
        for (int j = 0; j < arr.length; j++) {
            arr[j] = j;
        }
        // shuffle the data.
        for (int j = arr.length - 1; j >= 1 ; j--) {
            int p = rand.nextInt(j + 1);
            int v = arr[j];
            arr[j] = arr[p];
            arr[p] = v;
        }

        System.out.println("i="+size+", length="+arr.length);
        //System.out.println(Arrays.toString(arr));

        long startTime = System.nanoTime();
        SkippingLIS test = new SkippingLIS(arr);

        test.printLengthLIS();

        test.printNumOfLIS();
        long endTime = System.nanoTime();

        long totalTime = endTime - startTime;
        System.out.printf("It took me %.3fms.", totalTime / 1000000.0);

        test.printAllLIS(10);

        test = null;
        //System.out.println("available memory AFTER: " + java.lang.Runtime.getRuntime().freeMemory());
    }

    public static void main(String[] args) {
        SkippingLIS special = new SkippingLIS(new int[]{2,-3,4,90,-2,-1,-10,-9,-8});
        special.printAllLIS(10);

        Random rand = new Random();
        for(int i = 10; i < 100f; i++) {
            testSize(i, rand);
        }

        //testSize(10000000, rand);

    }

}

Answer 2

Note: This review is based on the (apparently incorrect) assumption that the sequence in question is 'contiguous'. In other words, the 'right solutions' in the example:

[2,-3,4,90,-2,-1,-10,-9,-8]

are:

[-3, 4, 90] and [-10, -9, -8]

In other words, the values have to appear next to each other in the data....

... this was not explicit in the question. Later comments indicate that the sequence can 'skip' values. The rules for 'skipping' appear to be that you can skip any value that is smaller than the first value in the sequence. The above example, if you include skipping has two additional solutions:

[2, 4, 90] and [-3, -2, -1]

---

There are a lot of things to cover here.... but, some forewarning, you have completely over-thought this problem.... and your algorithm is far from 'the right one'. Given that I am suggesting that the algorithm is overkill, there are two things I can do:

• go through what you have done, and point out general items that you should do differently that are related to things other than the algorithm.
• suggest an algorithm that is better.

General review

• Random data sets

  In your test method, you are building up a Set of random integer values. This set is not as random as you would think, though.... The Java implementation of HashSet does not make any guarantee about the order of the values as you retrieve them. Internally it uses a hashing system to build a table, and it stores the values in the table based on the hash, and then when you iterate over the values it returns them in an order that is essentially based on the way the data was hashed. So, as you store your random values, they are then being re-sorted in to the hash table, and then the return value is affected by this.

  You really should not be using the hash at all.... you should be using the primitive int-array, and saving yourself the extra step. But, your code looks like it is designed to ensure that there are no duplicates in your data... there are better ways to do that. Here is a simple insertion of a sequence of numbers, followed by a Fisher-Yates shuffle:

          // creates a random array of different integers
          int[] arr = new int[i];
          // set the values to be unique.
          for (int j = 0; j < arr.length; j++) {
              arr[j] = j;
          }
          // shuffle the data.
          for (int j = arr.length - 1; j >= 1 ; j--) {
              int p = rand.nextInt(j + 1);
              int v = arr[j];
              arr[j] = arr[p];
              arr[p] = v;
          }
  

  OK, that's a good way to get a bunch of int values that are unique, but are in a random order. It also only creates as many random numbers as are needed, it does not keep 'guessing' until it finds a unique value.

• Copying Arrays

  In your LIS constructor, you do the following to copy the input data:

  this.arr = new int[arr.length];
  System.arraycopy(arr, 0, this.arr, 0, arr.length);
  

  This can easily be replaced with the simpler helper-method from java.util.Arrays:

  this.arr = Arrays.copyOf(arr, arr.length);
  

• Method Naming

  Your method public int LISLength() should not be named with a capital letter to start. This is a 'getter' method, and should be named public int getLISLength()

Algorithm

Right, your algorithm. When I look at problems (things to review), I think: how would I solve this? I come up with a strategy, and then see if I can see the strategy in the code I am reviewing. If I can't see the strategy, I look harder, and try to determine what the strategy being used is... and I ask myself: Is it better than what I would have done?

In your case, I have to admit, I came up with a strategy, I could not see it in your code, and your strategy is so complicated, and you admit it is slow, that I actually have not figured out your code at all... it's too much effort to understand the intricacies when I know there's a much, much simpler way to do this.

This is a lesson for you... sometimes doing a google-search for an algorithm before trying to implement one is a good idea.

So, instead of trying to understand your algorithm properly, I am just going to demonstrate an alternate algorithm.....

The problem is:

• you have an array of values which are in no particular order.
• you need to identify sequences in that data where the values are increasing...
• you need to track how long the longest sequences are
• you need to track exaclty what the longest sequences are.

This can all be done in a single loop, with very little data needed to track the details.

Loop over the data... for each value:

• if the value is not increasing, then it is the start of a new sequence
• if the current sequence is longer than previous sequences, then we can forget all previous sequences, and we have a new longest sequence.
• if the current sequence is the same length as the longest sequence, then we need to remember where this sequence is.

I have put this all in a class, with a revised test to be more random.... For me, the code is running all the tests really fast. I had to change the time-monitoring code so that it counts in nanoseconds, instead of milliseconds. The 1000-entry test runs in 0.019ms. A test of 10 million integers took 75.608ms

here's the code that does the above:

import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Random;
import java.util.Set;

public class LIS {
    private final int[] copy;
    private final int[] startpoints;
    private final int longest;

    public LIS(int[] arr) {
        copy = new int[arr.length];
        int[] begin = new int[32];
        int seqcnt = 0;
        int seqlen = 0;
        int longseq = 0;
        int previous = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            int v = arr[i];
            // copy the data....
            copy[i] = v;
            if (v <= previous) {
                // not-increasing sequence
                seqlen = 0;
            }
            previous = v;
            seqlen++;
            if (seqlen > longseq) {
                // new longest sequence....
                longseq = seqlen;
                // throw away previous sequences.
                seqcnt = 0;
            }
            if (seqlen == longseq) {
                // new sequence.... matching the longest...
                if (seqcnt >= begin.length) {
                    // need more space to save this sequence.
                    begin = Arrays.copyOf(begin, begin.length * 2);
                }
                // at position `i - seqlen + 1` there begins a sequence that is all ascending.
                begin[seqcnt++] = i - seqlen + 1;
            }
        }
        longest = longseq;
        startpoints = Arrays.copyOf(begin, seqcnt);
    }

    public int longestLength() {// get exclusively the length of the LIS(s)
        return longest;
    }

    public void printLengthLIS() {
        System.out.println("LISs are " + longest + " integers long.");
    }
    public void printNumOfLIS() {
        System.out.println("There are " + startpoints.length + " LISs.");
    }
    public void printAllLIS() {
        System.out.println("All the LISs are: ");
        for (int sp : startpoints) {
            System.out.println(Arrays.toString(Arrays.copyOfRange(copy, sp, sp + longest)));
        }
    }

    private static final void testSize(int size, Random rand) {
        //System.out.println("available memory BEFORE: " + java.lang.Runtime.getRuntime().maxMemory());

        // creates a random array of different integers
        int[] arr = new int[size];
        for (int j = 0; j < arr.length; j++) {
            arr[j] = j;
        }
        // shuffle the data.
        for (int j = arr.length - 1; j >= 1 ; j--) {
            int p = rand.nextInt(j + 1);
            int v = arr[j];
            arr[j] = arr[p];
            arr[p] = v;
        }

        System.out.println("i="+size+", length="+arr.length);
        //System.out.println(Arrays.toString(arr));

        long startTime = System.nanoTime();
        LIS test = new LIS(arr);

        test.printLengthLIS();

        test.printNumOfLIS();
        long endTime = System.nanoTime();

        long totalTime = endTime - startTime;
        System.out.printf("It took me %.3fms.", totalTime / 1000000.0);

        test.printAllLIS();

        test = null;
        //System.out.println("available memory AFTER: " + java.lang.Runtime.getRuntime().freeMemory());
    }

    public static void main(String[] args) {
        Random rand = new Random();
        for(int i = 10; i < 1000; i++) {
            testSize(i, rand);
        }

        testSize(10000000, rand);
    }
}