首个最长递增子序列

Question

首个最长递增子序列

javaalgorithm

7

最长递增子序列是一个众所周知的问题，我有一个使用耐心算法的解决方案。

问题在于，我的解决方案给出了“最佳最长递增序列”，而不是出现的第一个最长递增序列。

区别在于第一个序列中的某些成员是更大的数字（但是序列长度完全相同）。

要获取第一个序列比预期的更难，因为拥有最佳序列并不容易转换为拥有第一个序列。

我想过先运行算法，然后找到长度为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());
      }

我改为存储索引，以便于需要再次访问原始数组。由于从索引到值的转换比相反方向更容易。

例如：

3 6 1 2 8

我的代码返回：1 2 8

第一个序列是：3 6 8

另一个例子：

1 5 2 3

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

基本上，如果第一个最长序列与最佳最长序列相同，则我的代码有效。但当有一堆长度相同的最长序列时，它会选择最好的而不是第一个。

- Helsing

1

有一个例子会更容易理解。 - Ole V.V.

2

如果你需要增长序列的长度，你需要的是起始索引、到目前为止最大值和当前值的长度。只有当你有更好的值时才会改变最大值。使用列表的列表看起来过于复杂。 - Wisthler

1

添加了一个例子以便澄清。 - Helsing

@Helsing，我的理解是你的序列可以有间隔？所以它们不一定是连续的？ - Lino

@mahieus的问题是我从未构建第一个和最长的序列。例如：3 6 1 2 8，我从未构建3 6 8，因为它被1、2等替换了。 - Helsing

显示剩余4条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nice_dev · Accepted Answer

代码自解释。(已添加注释，如果您需要额外的东西，请告诉我)。

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]