*First* Longest Increasing Subsequence

Question

The longest increasing subsequence is the well known problem and I have a solution with the patience algorithm.

Problem is, my solution gives me the "Best longest increasing sequence" instead of the First longest increasing sequence that appears.

The difference is that some of the members of the sequence are larger numbers in the first(but the sequence length is exactly the same).

Getting the first sequence is turning out to be quite harder than expected, because having the best sequence doesn't easily translate into having the first sequence.

I've thought of doing my algorithm then finding the first sequence of length N, but not sure how to.

So, how would you find the First longest increasing subsequence from a sequence of random integers?

My code snippet:

  public static void main (String[] args) throws java.lang.Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int inputInt;
        int[] intArr;

        try {
            String input = br.readLine().trim();
            inputInt = Integer.parseInt(input);
            String inputArr = br.readLine().trim();
            intArr = Arrays.stream(inputArr.split(" ")).mapToInt(Integer::parseInt).toArray();
        } catch (NumberFormatException e) {
            System.out.println("Could not parse integers.");
            return;
        }
        if(inputInt != intArr.length) {
            System.out.println("Invalid number of arguments.");
            return;
        }

        ArrayList<ArrayList<Integer>> sequences = new ArrayList<ArrayList<Integer>>();

        int sequenceCount = 1;
        sequences.add(new ArrayList<Integer>());
        sequences.get(0).add(0);

        for(int i = 1; i < intArr.length; i++) {
            for(int j = 0; j < sequenceCount; j++) {

                if(intArr[i] <= intArr[sequences.get(j).get(sequences.get(j).size() - 1)]) {
                    sequences.get(j).remove(sequences.get(j).size() - 1);
                    sequences.get(j).add(i);
                    break;
                } else if (j + 1 == sequenceCount) {
                    sequences.add(new ArrayList<Integer>(sequences.get(j)));
                    sequences.get(j + 1).add(i);
                    sequenceCount++;
                    break; //increasing sequenceCount causes infinite loop
                } else if(intArr[i] < intArr[sequences.get(j + 1).get(sequences.get(j + 1).size() - 1)]) {
                    sequences.set(j+ 1, new ArrayList<Integer>(sequences.get(j)));
                    sequences.get(j+ 1).add(i);
                    break;
                }
            }           
        }
        int bestSequenceLength = sequenceCount;
        ArrayList<Integer> bestIndexes = new ArrayList<Integer>(sequences.get(bestSequenceLength - 1));

        //build bestSequence, then after it I'm supposed to find the first one instead
        int[] bestSequence = Arrays.stream(bestIndexes.toArray()).mapToInt(x -> intArr[(int) x]).toArray();

       StringBuilder output = new StringBuilder("");
       for(Integer x : bestSequence) {
        output.append(x + " ");
       }
        System.out.println(output.toString().trim());
      }

I'm storing indexes instead in preparation for having to access the original array again. Since it's easier to go from indexes to values than vice versa.

Example:

3 6 1 2 8

My code returns: 1 2 8

First sequence is: 3 6 8

Another Example:

1 5 2 3

My code correctly returns: 1 2 3

Basically, my code works as long as the first longest sequence is the same as the best longest sequence. But when you have a bunch of longest sequences of the same length, it grabs the best one not the first one.

Answer 1

Code is self-explanatory. (Have added comments, let me know if you need something extra).

public class Solution {
    public static void main(String[] args) {
        int[] arr = {3,6,1,2,8};
        System.out.println(solve(arr).toString());
    }

    private static List<Integer> solve(int[] arr){
        int[][] data = new int[arr.length][2];
        int max_length = 0;
        // first location for previous element index (for backtracing to print list) and second for longest series length for the element
        for(int i=0;i<arr.length;++i){
            data[i][0] = -1; //none should point to anything at first
            data[i][1] = 1;
            for(int j=i-1;j>=0;--j){
                if(arr[i] > arr[j]){
                    if(data[i][1] <= data[j][1] + 1){ // <= instead of < because we are aiming for the first longest sequence
                        data[i][1] = data[j][1] + 1;
                        data[i][0] = j;
                    }
                }
            }

            max_length = Math.max(max_length,data[i][1]);
        }

        List<Integer> ans = new ArrayList<>();

        for(int i=0;i<arr.length;++i){
            if(data[i][1] == max_length){
                int curr = i;
                while(curr != -1){
                    ans.add(arr[curr]);               
                    curr = data[curr][0];
                }                
                break;
            }
        }

        Collections.reverse(ans);// since there were added in reverse order in the above while loop
        return ans;
    }    
}

Output:

[3, 6, 8]