تصف هذه المقالة تنفيذ Java لأطول خوارزمية اللاحقة للصفائف. شاركه للرجوع إليه ، على النحو التالي:
المشكلة: بالنظر إلى مجموعة من الطول n ، ابحث عن أطول التسلسل التلقائي التلقائي (ليس بالضرورة مستمر ، ولكن لا يمكن إفساد الترتيب). على سبيل المثال: أعطيت مجموعة من الطول A {1 ، 3 ، 5 ، 2 ، 4 ، 6 ، 7 ، 8} بطول 8 ، ثم أطول تسلسل amplicon هو {1 ، 2 ، 4 ، 6 ، 7 ، 8} وطوله هو 6.
الفكرة 1: عندما ترى السؤال في البداية ، سيفكر الكثير من الناس بالتأكيد في LCS في المرة الأولى. قم أولاً بفرز الصفيف إلى صفيف جديد ، ثم استخدم المصفوفة الجديدة والمصفوفة الأصلية للعثور على LCS للحصول على الإجابة. يمكن أن يتخيل الكثير من الناس هذا الحل ، لذلك لن أخوض في التفاصيل.
الفكرة 2: وفقًا لفكرة الفكرة 1 ، لا يزال يتعين عليك استخدام DP عندما تجد LCS أخيرًا. لماذا لا نستخدم DP لحلها مباشرة؟ بالنسبة إلى Array ARR ، فإننا نعبر الصفيف من الخلف إلى الأمام ، ونجد أطول وقت لاحق عندما ينتهي اللاحق بـ arr[i] ، ثم نأخذ القيمة القصوى فيه. يمكنك الحصول على أطول بعد الصفيف بأكمله. فكيف تجد أطول فترة تنتهي مع arr[i] ؟ يتم تحويل هذا إلى مشكلة DP. لتتطلب أطول فترة من arr[i] ، تحتاج فقط إلى العثور على أطول فترة من arr[i-1] . هذا هو: max{arr[i]}=max{arr[i-1]}+1 .
رمز تنفيذ Java:
الفئة العامة 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 ؛ ] 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) ؛ } int 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) ؛ . int notcontainlen = dp (newarr ، end) ؛ الإرجاع ContaSlen> notcontainlen؟ ContaSlen: notcontainlen ؛ }} // إذا لم يتم العثور على أصغر من النهاية ، فإن طول الإرجاع هو 0 إرجاع 0 ؛ }}نتائج التشغيل:
6
قد تشغل طريقتي مساحة كبيرة لأن صفائف جديدة متعددة تم فتحها في الوسط ، لكنني لا أعتقد أنها كثيرًا - لم أحسبها. إذا كان هناك أي خطأ ، يرجى تصحيحه.
لمزيد من المعلومات حول خوارزميات Java ، يمكن للقراء المهتمين بهذا الموقع عرض الموضوعات: "بنية بيانات Java وبرنامج تعليمي الخوارزمية" ، "ملخص" Tips Java ".
آمل أن يكون هذا المقال مفيدًا لبرمجة Java للجميع.