この記事では、配列の最長サブセンセンスアルゴリズムのJava実装について説明します。次のように、参照のために共有してください。
問題：長さnの配列を考えると、最長の単調な自動侵入サブシーケンスを見つけます（必ずしも連続しているわけではありませんが、順序を台無しにすることはできません）。たとえば、長さ8の長さa {1、3、5、2、4、6、7、8}の配列がある場合、その最長単調アンプリコンシーケンスは{1、2、4、6、7、8}で、その長さは6です。
アイデア1：最初に質問を見ると、多くの人が間違いなくLCSを最初に考えるでしょう。最初に配列を新しい配列に並べ替えてから、新しい配列と元の配列を使用してLCSを見つけて答えを得ます。多くの人がこの解決策を想像できるので、私は詳細を説明しません。
アイデア2：アイデア1のアイデアによると、最終的にLCSを見つけたときはDPを使用する必要があります。 DPを使用して直接解決しないのはなぜですか？配列arrの場合、配列を後ろから前後に通過させ、サブシーケンスがarr[i]で終了したときに最長のサブシーケンスを見つけ、その中で最大値を取得します。配列全体の最長のサブシーケンスを取得できます。では、 arr[i]で終わる最長のサブシーケンスを見つけるにはどうすればよいですか？これはDP問題に変換されます。 arr[i]の最長サブシーケンスを要求するには、 arr[i-1]の最長サブセンシングを見つけるだけで必要です。つまり、 max{arr[i]}=max{arr[i-1]}+1 。
Java実装コード：
public class arrdemo {public static void main（string [] args）{// int [] arr = {89、256、78、1、46、78、8}; int [] arr = {1、3、5、2、4、6、7、8}; // int [] arr = {6、4、8、2、17}; int max = 0; int maxlen = arr.length; //アレイを後ろからフォワードに移動し、（int i = arr.length-1; i> 0; i-）のarr [i]で終了するときに最も長いサブシーケンス長を見つけます。 System.ArrayCopy（arr、0、newarr、0、i）; int currentLength = 1 + dp（newarr、arr [i]）; if（currentlength> max）max = currentLength; //最長サブシーケンスの最長の長さは、元の配列の長さです//最長サブセンセンスの要素を見つける必要がないため、ループを直接終了して、（max == maxlen）ブレイクの場合、時間オーバーヘッドを短縮します。 } system.out.println（max）; } public static int dp（int [] arr、int end）{//再帰末端条件（arr.length == 1）{//終了未満の場合、サブシーケンスに含まれ、サブシーケンス+1 if（arr [0] <= end）return 1;それ以外の場合は0を返します。 } //配列をトラバースして、端に最も近い要素位置を見つけます。 System.ArrayCopy（arr、0、newarr、0、i）; // arr [i]を含む場合の最長サブシーケンスと、それぞれarr [i]を含む場合の最長サブシーケンスを計算し、最大値int containslen = dp（newarr、arr [i]） + 1を取得します。 int notcontainlen = dp（newarr、end）; return containslen> notcontainlen？ containslen：notcontainlen; }} // endよりも小さくない場合、戻り長さは0の戻り値です。 }}実行結果：
6
私の方法は、真ん中に複数の新しい配列が開かれているため、多くのスペースを占有する可能性がありますが、それはあまりないと思います - 私はそれをカウントしていません。何か問題がある場合は、修正してください。
Javaアルゴリズムの詳細については、このサイトに興味のある読者は、「Javaデータ構造とアルゴリズムのチュートリアル」、「Java操作DOMノードのヒントの要約」、「Javaファイルの要約およびディレクトリ操作のヒント」、「Java Cache操作のヒントの要約」というトピックを見ることができます。
この記事がみんなのJavaプログラミングに役立つことを願っています。