*第一*最长递增子序列

Question

最长增子序列是我们熟知的问题，我用耐心算法给出了一个解决方案。

我曾想过先用我的算法，然后找到长度为N的第一个序列，但不知道该怎么做。

那么，如何从随机整数序列中找到第一个最长的递增子序列呢？

我的代码段：

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

我的代码返回：1 2 8

第一个序列是：3 6 8

另一个例子：

我的代码正确返回：1 2 3

基本上，只要第一个最长序列与最佳最长序列相同，我的代码就能工作。但是当你有一堆相同长度的最长序列时，它会抓住最好的一个，而不是第一个。

Answer 1

代码是不言自明的。（有添加的评论，让我知道，如果你需要一些额外的东西）。

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

输出：

[3, 6, 8]