لنفترض أن هناك تسلسلات: 2 ، 1 ، 3 ، 5 ، تجد أن أطول تسلسل تصاعدي هو 2 ، 3 ، 5 أو 1 ، 3 ، 5 ، والطول هو 3.
فكرة خوارزمية LIS هي:
لنفترض أن هناك تسلسل أ.
① إذا كان هناك عنصر واحد فقط ، فإن طول تسلسل أسرني أطول هو 1 ؛
② إذا كان هناك عنصرين ، إذا كان [1]> A [0] ، فإن طول تسلسل Ascender الأطول هو 2 ، A [1] هو العنصر الأخير من أطول تسلسل تصاعدي ؛ إذا كان [1] <A [0] ، وطول أطول تسلسل صعود هو 1 ، و A [0] و A [1] هما العنصر الأخير من أطول تسلسل الصعود.
③ إذا كان مصنوعًا من ثلاثة عناصر ، إذا كان A [2]> A [0] ، A [2]> A [1] ، يمكن أن يكون A [2] العنصر الأخير من أطول التسلسل الفرعي تصاعدي حيث يوجد [0] أو A [1]. ثم أي تسلسل للاختيار يعتمد على التسلسل A [0] و A [1] أطول.
④ للتوسع في عناصر n ، فإنه هو رؤية طول تسلسل أسرع مع [n] كعنصر آخر.
تحديد صفائف اثنين ، واحد هو A والآخر ب.
يخزن A للبيانات الأصلية ، ويخزن B [i] طول أسوأ تسلسل الصعود الذي ينتهي بـ A [i].
الرمز كما يلي:
class lmax {public static void lmax (int [] a ، int [] b) {b [0] = 1 ؛ لـ (int i = 1 ؛ i <a.length ؛ i ++) {int countmax = 0 ؛ لـ (int j = 0 ؛ j <i ؛ j ++) {if (a [i]> a [j] && b [j]> countmax) {countmax = b [j] ؛ // قم بتسجيل طول اللاحقة التي تكون قيمة العنصر فيها أصغر من [i] ولكنها تتوافق مع أطول وقت لاحق}} b [i] = countmax+1 ؛ // أطول طول اللاحقة المقابلة لـ A [i]}}}2. اخرج من التكوين
وصف العنوان:
عندما تكون في المدرسة الثانوية ، نظمت المدرسة جميع المعلمين والطلاب للركض كل صباح لممارسة الرياضة. كلما بدا ترتيب التمرين ، بدأ الجميع يركضون في الطابق السفلي ، ثم تم تصطفها على القصر أمام الخط ، بينما كانت الأطول تصطف في نهاية الخط. فجأة ، في يوم من الأيام ، توصل الشخص المسؤول عن الفريق إلى فكرة وأراد تغيير التكوين. هذا هو ، عندما هرب الجميع من الطابق العلوي ، كان جميع الطلاب مشغولين بشكل عشوائي على التوالي ، وكان الشخص المسؤول عن الفريق قد أخرج جزءًا من الطلاب من الفريق ، بحيث كان ارتفاع الطلاب الباقين في الفريق شكلًا "ذروة" الذي ارتفع أولاً ثم سقط من الجبهة. يقال إن مثل هذا الشكل يمكن أن يجلب حظًا سعيدًا للجميع ، وأتمنى لكم جميعًا أن تتسلق القمة على طريق التعلم. (لاحظ أن جانبًا واحدًا فقط من الجبل يلبي الظروف ، مثل 1 و 1 و 2 و 2 و 1 يلتقي بالشروط)
يدخل:
قد يحتوي الإدخال على عينات اختبار متعددة.
لكل حالة اختبار ، فإن السطر الأول الذي تم إدخاله هو عدد صحيح N (1 <= n <= 1000000): يمثل عدد الطلاب المراد إدخالهم.
يشمل السطر الثاني من المدخلات الأعداد الصحيحة n: يمثل ارتفاع الطالب (CM) (عدد صحيح إيجابي مع ارتفاع لا يزيد عن 200).
الإخراج:
لكل حالة اختبار ، يكون الحد الأدنى لعدد الطلاب المراد رسمه هو الإخراج.
إدخال عينة:
6
100 154 167 159 132 105
5
152 152 152 152 152 152
إخراج العينة:
0
4
عند استخدام LIS لحل هذه المشكلة ، يمكنك النظر في هذا:
أولاً ، استخدم LIS للعثور على طول تسلسل أسرع أطول ينتهي مع كل عنصر من الأمام إلى الخلف ، ثم استخدم LIS للعثور على طول تسلسل Ascender أطول مع كل عنصر.
احصل على صفيفتين B1 ، B2.
B1 و B2 المقابلان للإضافة المقابلة وطرح واحد متكرر هو أطول "جبل".
Public Class Peak {public static void main (string [] args) {int n ؛ int re ؛ do {Scanner in = new Scanner (system.in) ؛ n = in.nextint () ؛ } بينما (n <0 || n> 100000) ؛ int [] a = new int [n] ؛ // Array Array int [] ar = new int [n] ؛ // الماسح الضوئي الصفيف العكسي في = ماسح ضوئي جديد (System.in) ؛ لـ (int i = 0 ؛ i <n ؛ i ++) {a [i] = in.nextint () ؛ } int [] b1 = new int [n] ؛ suppressWarnings ("غير مستخدم") int [] b2 = new int [n] ؛ lmax.lmax (a ، b1) ؛ ar = revers.reverse (a) ؛ lmax.lmax (ar ، b2) ؛ // حل أطول وقت تصاعدي للصفقة العكسية B2 = عكس. // معكوس الأطول الإطار الصعودي للمصفوفة العكسية لإضافة ما هو المقابل لأطول فترة تصاعدية للمصفوفة الأصلية re = result.result (b1 ، b2) ؛ system.out.print (re) ؛ }} <br> <br> <br> <br> نتيجة الفئة {public static int result (int [] a ، int [] b) {int max = 0 ؛ int [] c = new int [A.Length] ؛ لـ (int i = 0 ؛ i <a.length ؛ i ++) {c [i] = a [i]+b [i] ؛ } arrays.sort (c) ؛ max = c [c.length-1] -1 ؛ // الشخص المقابل مع أطول إضافة وطرح العائد المتكرر A.Length-Max ؛ }}ما سبق هو كل محتوى مشكلة استخدام Java لتنفيذ خوارزمية LIS وتكوينات صنع. آمل أن يكون ذلك مفيدًا للجميع ودعم wulin.com أكثر ~