时间戳

首页 > 解决方案 > *First* 最长递增子序列

java - *First* 最长递增子序列

问题描述

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

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

不同之处在于序列的某些成员在第一个中是较大的数字（但序列长度完全相同）。

获得第一个序列比预期的要困难得多，因为拥有最好的序列并不容易转化为拥有第一个序列。

我想过做我的算法，然后找到长度为 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

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

标签： javaalgorithm

解决方案

代码是不言自明的。（添加了评论，如果您需要额外的东西，请告诉我）。

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]

推荐阅读