シーケンスがあるとします:2、1、3、5、最長のアセンダーシーケンスが2、3、5または1、3、5であり、長さは3であることがわかります。
LISアルゴリズムのアイデアは次のとおりです。
シーケンスaがあるとします。
element要素が1つしかない場合、最長のアセンダーシーケンスの長さは1です。
a [1]> a [0]の2つの要素がある場合、最長のascenderシーケンスの長さは2である場合、[1]は最長のアセンダーシーケンスの最後の要素です。 [1] <a [0]の場合、最も長いアセンダーシーケンスの長さは1で、[0]とa [1]はどちらもその最長のアセンダーシーケンスの最後の要素です。
a [2]> a [0]、[2]> a [1]、[2]、a [2]が[0]または[1]が配置される最も長い昇順のサブシーケンスの最後の要素になります。次に、選択するシーケンスは、どのシーケンスA [0]と[1]が長くなるかによって異なります。
n要素に拡張するために、a [n]が最後の要素として、最も長いアセンダーシーケンスの長さを確認することです。
2つの配列を定義します。1つはa、もう1つはbです。
Aは元のデータを保存し、B [i]は[i]で終わる最長のアセンダーシーケンスの長さを保存します。
コードは次のとおりです。
class lmax {public static void lmax(int [] a、int [] b){b [0] = 1; for(int i = 1; i <a.length; i ++){int countmax = 0; for(int j = 0; j <i; j ++){if(a [i]> a [j] && b [j]> countmax){countmax = b [j]; //要素値がa [i]より小さいが、最長サブシーケンスに対応するサブシーケンス長を記録}} b [i] = countmax+1; // [i]に対応する最長サブシーケンス長は}}}2。フォーメーションから出ます
タイトル説明:
高校にいるとき、学校はすべての教師と生徒を組織し、毎朝運動するために走りました。運動命令が鳴るたびに、誰もが階下で走り始め、それから短いハイテッドのものはラインの前に並んでいて、背の高いものがラインの端に並んでいた。突然、ある日、チームを担当する人がアイデアを思いつき、フォーメーションを変えたいと思った。つまり、全員が上層階から駆け落ちたとき、すべての学生がランダムに連続して占領され、チームの担当者はチームの学生の一部を奪い、チームの残りの生徒の高さは最初に上昇し、その後前から落ちた「ピーク」の形になりました。そのような形が誰にも幸運をもたらすことができると言われており、私は皆さんが学習の道のトップに登ることを願っています。 (1、1、2、2、1などの条件を満たしている山の片側のみが条件を満たしていることに注意してください)
入力:
入力には複数のテストサンプルが含まれる場合があります。
各テストケースについて、入力された最初の行は整数n(1 <= n <= 1000000)です。入力する学生の数を表します。
入力の2番目の行には、N整数が含まれます。学生の高さ(cm)を表します(高さは200以下の高さの正の整数)。
出力:
各テストケースについて、描画される学生の最小数は出力です。
サンプル入力:
6
100 154 167 159 132 105
5
152 152 152 152 152 152
サンプル出力:
0
4
LISを使用してこの問題を解決する場合、これを考慮することができます。
まず、LISを使用して、各要素で前後に終了する最長のアセンダーシーケンスの長さを見つけてから、LISを使用して、各要素で終了する最長のアセンダーシーケンスの長さを見つけます。
2つの配列B1、B2を取得します。
対応する添加に対応し、繰り返されるものを差し引くことに対応するB1とB2は、最も長い「山」です。
public class peak {public static void main(string [] args){int n; int re; {scanner in = new Scanner(system.in); n = in.nextint(); } while(n <0 || n> 100000); int [] a = new int [n]; //元の配列int [] ar = new int [n]; //逆配列スキャナーin = new Scanner(system.in); for(int i = 0; i <n; i ++){a [i] = in.nextint(); } int [] b1 = new int [n]; @suppresswarnings( "unused")int [] b2 = new int [n]; lmax.lmax(a、b1); AR = reverse.Reverse(a); lmax.lmax(ar、b2); //逆配列の最長昇順のサブシーケンスを解きますb2 = reverse.Reverse(b2); //逆配列の最も長い昇順のサブシーケンスを逆逆数元の配列の最長の昇順のサブセンシティに対応する対応するサブシーケンスを追加します。 System.out.print(re); }} <br> <br> <br> <br> class result {public static int result(int [] a、int [] b){int max = 0; int [] c = new int [a.length]; for(int i = 0; i <a.length; i ++){c [i] = a [i]+b [i]; } arrays.sort(c); max = c [c.length-1] -1; //最長の追加と繰り返しのリターンを差し引く対応する人。 }}上記は、Javaを使用してLISアルゴリズムを実装し、フォーメーションを作成するという問題のすべての内容です。私はそれがすべての人に役立ち、wulin.comをもっとサポートすることを願っています〜