最も長いサブシーケンスの問題 - ナイーブなアプローチ

Question

私は動的プログラミングの基礎を学び、questionの配列で最長増加サブシーケンスを見つけました。 DPソリューションを調べる前に、自分でコードを作成し、次のアルゴリズムを考え出しました。完全なコードはhereです。

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

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（時間制限超過エラー）と間違った回答の両方が発生します。効率的なソリューションはDP O（nlogn）ソリューションなので、私はTLEエラーを理解していますが、私はこのアルゴリズムによって生成された間違った答えについて混乱しています。そのようなケースの入力は大きすぎるので（〜10000）、ソリューションがどこに間違っているかを手動で確認することはできません。

完全なコードに加えて、データセットの1つへの出力はhereです。 HackerRankによって報告された正解は195でなければなりません。

Answer 1

解決策に問題が見つかりました。この問題は、問題文を慎重に読んでいないためです。

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