บทความนี้อธิบายถึงการใช้งาน Java ของอัลกอริทึมที่ยาวที่สุดที่ยาวที่สุดสำหรับอาร์เรย์ แบ่งปันสำหรับการอ้างอิงของคุณดังนี้:
ปัญหา: ให้ความยาวอาร์เรย์ n ให้ค้นหาลำดับย่อย autoincrement ที่ยาวที่สุด (ไม่จำเป็นต้องต่อเนื่อง แต่คำสั่งไม่สามารถทำให้สับสน) ตัวอย่างเช่น: ให้อาร์เรย์ที่มีความยาว A {1, 3, 5, 2, 4, 6, 7, 8} ที่มีความยาว 8 จากนั้นลำดับแอมพลิฟายเออร์โมโนโทนิกที่ยาวที่สุดคือ {1, 2, 4, 6, 7, 8} และความยาวของมันคือ 6
ความคิดที่ 1: เมื่อคุณเห็นคำถามในตอนแรกหลายคนจะนึกถึง LCS ก่อน ก่อนอื่นเรียงลำดับอาร์เรย์เป็นอาร์เรย์ใหม่จากนั้นใช้อาร์เรย์ใหม่และอาร์เรย์ดั้งเดิมเพื่อค้นหา LCS เพื่อรับคำตอบ หลายคนสามารถจินตนาการถึงวิธีแก้ปัญหานี้ได้ดังนั้นฉันจะไม่เข้าไปดูรายละเอียด
แนวคิด 2: ตามแนวคิดของ Idea 1 คุณยังต้องใช้ DP เมื่อคุณพบ LCS ในที่สุด ทำไมเราไม่ใช้ DP เพื่อแก้ปัญหาโดยตรง สำหรับอาร์เรย์ arr เราสำรวจอาร์เรย์จากด้านหลังไปด้านหน้าและค้นหาลำดับที่ยาวที่สุดเมื่อภาคต่อท้ายด้วย arr[i] จากนั้นใช้ค่าสูงสุดในนั้น คุณสามารถได้รับที่ยาวที่สุดของอาร์เรย์ทั้งหมด ดังนั้นวิธีการค้นหาลำดับที่ยาวที่สุดที่ลงท้ายด้วย arr[i] ? สิ่งนี้ถูกแปลงเป็นปัญหา DP ในการกำหนดระยะเวลาที่ยาวที่สุดของ arr[i] คุณจะต้องค้นหาลำดับที่ยาวที่สุดของ arr[i-1] นั่นคือ: max{arr[i]}=max{arr[i-1]}+1
รหัสการใช้งาน Java:
คลาสสาธารณะ arrdemo {โมฆะสาธารณะคงที่หลัก (สตริง [] 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; // สำรวจอาร์เรย์จากด้านหลังไปข้างหน้าและค้นหาความยาวตามลำดับที่ยาวที่สุดเมื่อลงท้ายด้วย arr [i] สำหรับ (int i = arr.length-1; i> 0; i--) {int [] newarr = new int [i]; System.arrayCopy (arr, 0, Newarr, 0, i); int currentLength = 1 + dp (newarr, arr [i]); if (currentLength> สูงสุด) สูงสุด = currentLength; // ความยาวที่ยาวที่สุดของลำดับที่ยาวที่สุดคือความยาวของอาร์เรย์ดั้งเดิม // เพราะเราไม่จำเป็นต้องค้นหาองค์ประกอบของลำดับที่ยาวที่สุดเราจะสิ้นสุดลูปโดยตรงเพื่อลดค่าใช้จ่ายเหนือศีรษะถ้า (max == maxlen) } system.out.println (สูงสุด); } public Static int dp (int [] arr, int end) {// เงื่อนไขสิ้นสุดแบบเรียกซ้ำถ้า (arr.length == 1) {// ถ้าน้อยกว่าสิ้นสุดมันจะรวมอยู่ในลำดับความยาวของลำดับที่ต่อมา +1 ถ้า (arr [0] <= สิ้นสุด) กลับ 1; กลับมาอีก 0; } // สำรวจอาร์เรย์และค้นหาตำแหน่งองค์ประกอบที่อยู่ใกล้ที่สุดจนจบและ <= สิ้นสุด i สำหรับ (int i = arr.length-1; i> = 0; i--) {ถ้า (arr [i] <= end) {// ตัดทอนอาร์เรย์จากฉันใหม่ System.arrayCopy (arr, 0, Newarr, 0, i); // คำนวณลำดับที่ยาวที่สุดเมื่อมี arr [i] และลำดับที่ยาวที่สุดเมื่อไม่มี arr [i] ตามลำดับและใช้ค่าสูงสุด int containlen = dp (newarr, arr [i]) + 1; int notContainLen = dp (newarr, end); ส่งคืน containlen> notcontainlen? CONTASSLEN: NOTCONTAINLEN; }} // หากไม่พบน้อยกว่าสิ้นสุดความยาวผลตอบแทนคือ 0 return 0; -ผลการทำงาน:
6
วิธีการของฉันอาจใช้พื้นที่มากเพราะมีอาร์เรย์ใหม่หลายแห่งเปิดอยู่ตรงกลาง แต่ฉันไม่คิดว่ามันจะมาก - - ฉันไม่ได้นับเลย หากมีอะไรผิดปกติโปรดแก้ไข
สำหรับข้อมูลเพิ่มเติมเกี่ยวกับอัลกอริทึม Java ผู้อ่านที่มีความสนใจในเว็บไซต์นี้สามารถดูหัวข้อ: "โครงสร้างข้อมูล Java และการสอนอัลกอริทึม", "บทสรุปของเคล็ดลับการดำเนินงาน Java Dom", "บทสรุปของไฟล์ Java และเคล็ดลับการดำเนินการไดเรกทอรี" และ "สรุป
ฉันหวังว่าบทความนี้จะเป็นประโยชน์กับการเขียนโปรแกรม Java ของทุกคน