0

私は動的プログラミングの基礎を学んでいて、配列内の最長増加部分列を見つけるという問題に行き着きました。DP ソリューションを調べる前に、自分でコーディングすることにし、次のアルゴリズムを思いつきました。完全なコードは、こちら にあります。

アイデアは、リスト配列を作成して増加するすべてのサブシーケンスを格納し、各サブシーケンスの対​​応する最大値を格納して比較を高速化することです。

private void findLIS(int[] inputArr) {
    List[] listOfSubs = new ArrayList[inputArr.length];    //Max different subsequences in an array would be N
    //To store the max value of each of the subsequences found yet
    List<Integer> maxValList = new ArrayList<Integer>();
    listOfSubs[0] = new ArrayList<Integer>();
    listOfSubs[0].add(inputArr[0]);    //Add the first element of the array to the list
    maxValList.add(inputArr[0]);

    for (int i=1;i<inputArr.length;i++) {
        boolean flag = false;
        int iter=0;

        //Compare inputArr[i] with the maxVal of each subsequence
        for (int j=0; j<maxValList.size(); j++) {
            if (inputArr[i]>maxValList.get(j)) {
                maxValList.set(j, inputArr[i]); //Update the maxVal in the corresponding position in the list
                listOfSubs[j].add(inputArr[i]);
                flag = true;
            }
            iter = j;
        }
        //If inputArr[i] is not greater than any previous values add it to a new list
        if (!flag) {
            maxValList.add(inputArr[i]);
            listOfSubs[iter+1] = new ArrayList<Integer>();
            listOfSubs[iter+1].add(inputArr[i]);
        }
    }

    //Finding the maximum length subsequence among all the subsequences
    int max=0, iter=0, index=0;
    for (List<Integer> lst : listOfSubs) {
        if (lst!=null && lst.size() > max) {
            max = lst.size();
            index=iter;
        }
        iter++;
    }

    //Print the longest increasing subsequence found
    System.out.println("The Longest Increasing Subsequence is of length " + listOfSubs[index].size() +
            " and is as follows:");
    for (int i=0;i<listOfSubs[index].size();i++) {
        System.out.print(listOfSubs[index].get(i) + " ");
    }
}

コードは O(n^2) 時間で実行され、小規模/中規模の入力に対して完全に機能します。ただし、一部のオンライン プラクティス ポータル ( HackerRankなど) に対してコードを実行しようとすると、TLE (Time Limit Exceeded Errors) と Wrong Answer の両方が表示されます。効率的なソリューションは DP O(nlogn) ソリューションであるため、TLE エラーは理解していますが、このアルゴリズムによって生成される間違った回答について混乱しています。このような場合の入力は大きすぎる (~10000) ため、解決策がどこでうまくいかないかを手動で確認することはできません。

完全なコードとデータ セットの 1 つへの出力は、ここにあります。正解は、HackerRank によって報告された 195 である必要があります。

4

1 に答える 1

1

私は私の解決策に問題を見つけました。問題は、問題文を注意深く読んでいないことにあります。

入力が {3, 2, 6, 4, 5, 1} であるとします。コードではシーケンス {3,6} と {2,6} のみを考慮し、シーケンス {2,4,5} または {3,4,5} は考慮しません。したがって、すべての反復で、前のサブシーケンスの最大値よりも大きい数を見つけた場合、それをそのようなすべてのサブシーケンスに追加して、後者のサブシーケンスに到達する可能性を減らします。

于 2016-08-30T17:20:59.117 に答える