สมมติว่ามีลำดับ: 2, 1, 3, 5, พบว่าลำดับทางขึ้นที่ยาวที่สุดคือ 2, 3, 5 หรือ 1, 3, 5 และความยาวคือ 3
แนวคิดของอัลกอริทึม LIS คือ:
สมมติว่ามีลำดับ
①หากมีเพียงองค์ประกอบเดียวความยาวของลำดับทางขึ้นที่ยาวที่สุดคือ 1;
②หากมีสององค์ประกอบถ้า a [1]> a [0] ความยาวของลำดับทางขึ้นที่ยาวที่สุดคือ 2, a [1] เป็นองค์ประกอบสุดท้ายของลำดับการขึ้นเครื่องที่ยาวที่สุด; ถ้า A [1] <a [0] ความยาวของลำดับทางขึ้นที่ยาวที่สุดคือ 1 และ A [0] และ A [1] เป็นทั้งองค์ประกอบสุดท้ายของลำดับทางขึ้นที่ยาวที่สุด
③ถ้ามันทำจากสามองค์ประกอบถ้า a [2]> a [0], a [2]> a [1] ดังนั้น [2] อาจเป็นองค์ประกอบสุดท้ายของลำดับย่อยที่ยาวที่สุดที่ยาวที่สุดโดยที่ [0] หรือ A [1] ตั้งอยู่ จากนั้นลำดับที่จะเลือกขึ้นอยู่กับลำดับ A [0] และ A [1] นานกว่า
④เพื่อขยายไปยังองค์ประกอบ N มันคือการดูความยาวของลำดับทางขึ้นที่ยาวที่สุดด้วย A [n] เป็นองค์ประกอบสุดท้าย
กำหนดสองอาร์เรย์หนึ่งคือ A และอีกอันคือ B
จัดเก็บข้อมูลต้นฉบับและ B [I] เก็บความยาวของลำดับทางขึ้นที่ยาวที่สุดซึ่งลงท้ายด้วย [I]
รหัสมีดังนี้:
คลาส lmax {โมฆะคงที่สาธารณะ lmax (int [] a, int [] b) {b [0] = 1; สำหรับ (int i = 1; i <a.length; i ++) {int countmax = 0; สำหรับ (int j = 0; j <i; j ++) {ถ้า (a [i]> a [j] && b [j]> countmax) {countmax = b [j]; // บันทึกความยาวที่ตามมาซึ่งค่าองค์ประกอบมีขนาดเล็กกว่า [i] แต่สอดคล้องกับลำดับที่ยาวที่สุด}} b [i] = countmax+1; // ความยาวต่อมาที่ยาวที่สุดที่สอดคล้องกับ [i] คือ}}}2. ออกไปจากการก่อตัว
ชื่อคำอธิบาย:
เมื่ออยู่ในโรงเรียนมัธยมโรงเรียนได้จัดครูและนักเรียนทุกคนให้ทำงานทุกเช้าเพื่อออกกำลังกาย เมื่อใดก็ตามที่คำสั่งการออกกำลังกายดังขึ้นทุกคนเริ่มวิ่งลงไปชั้นล่างและจากนั้นคนที่มีความสูงสั้นก็เรียงรายอยู่ด้านหน้าของเส้นในขณะที่คนที่สูงกว่าถูกเรียงรายไปหมดในตอนท้ายของบรรทัด ทันใดนั้นวันหนึ่งบุคคลที่รับผิดชอบทีมก็มีความคิดและต้องการเปลี่ยนการก่อตัว นั่นคือเมื่อทุกคนวิ่งลงมาจากชั้นบนนักเรียนทุกคนถูกสุ่มอยู่แถวหนึ่งและบุคคลที่รับผิดชอบทีมได้นำส่วนหนึ่งของนักเรียนจากทีมออกมาเพื่อให้ความสูงของนักเรียนที่เหลือในทีมเป็นรูปร่าง "จุดสูงสุด" ที่เพิ่มขึ้นก่อนแล้วก็ตกลงมาจากด้านหน้า ว่ากันว่ารูปร่างดังกล่าวสามารถนำโชคดีมาให้ทุกคนและฉันขอให้ทุกคนปีนขึ้นไปบนถนนแห่งการเรียนรู้ (หมายเหตุมีเพียงด้านเดียวของภูเขาที่ตรงกับเงื่อนไขเช่น 1, 1, 2, 2 และ 1 ตรงตามเงื่อนไข)
เข้า:
อินพุตอาจมีตัวอย่างทดสอบหลายตัวอย่าง
สำหรับแต่ละกรณีการทดสอบบรรทัดแรกที่ป้อนคือจำนวนเต็ม n (1 <= n <= 10,00000): แสดงจำนวนนักเรียนที่จะป้อน
บรรทัดที่สองของอินพุตรวมถึงจำนวนเต็ม N: แสดงถึงความสูงของนักเรียน (CM) (จำนวนเต็มบวกที่มีความสูงไม่สูงกว่า 200)
เอาท์พุท:
สำหรับแต่ละกรณีการทดสอบจำนวนนักเรียนขั้นต่ำที่จะถูกดึงจะถูกส่งออก
อินพุตตัวอย่าง:
6
100 154 167 159 132 105
5
152 152 152 152 152 152
ตัวอย่างเอาท์พุท:
0
4
เมื่อใช้ LIS เพื่อแก้ปัญหานี้คุณสามารถพิจารณาสิ่งนี้:
ก่อนอื่นให้ใช้ LIS เพื่อค้นหาความยาวของลำดับทางขึ้นที่ยาวที่สุดที่ลงท้ายด้วยแต่ละองค์ประกอบจากด้านหน้าไปด้านหลังจากนั้นใช้ LIS เพื่อค้นหาความยาวของลำดับทางขึ้นที่ยาวที่สุดที่ลงท้ายด้วยแต่ละองค์ประกอบ
รับสองอาร์เรย์ b1, b2
B1 และ B2 ที่สอดคล้องกับการเพิ่มที่สอดคล้องกันและการลบสิ่งที่ทำซ้ำเป็น 'ภูเขา' ที่ยาวที่สุด
ระดับสูงสุดระดับสาธารณะ {โมฆะคงที่สาธารณะหลัก (สตริง [] args) {int n; int re; ทำ {สแกนเนอร์ใน = ใหม่สแกนเนอร์ (System.in); n = in.nextint (); } ในขณะที่ (n <0 || n> 100000); int [] a = new int [n]; // อาร์เรย์ดั้งเดิม int [] ar = new int [n]; // สแกนเนอร์อาร์เรย์ผกผันใน = สแกนเนอร์ใหม่ (System.in); สำหรับ (int i = 0; i <n; i ++) {a [i] = in.nextint (); } int [] b1 = int ใหม่ [n]; @suppresswarnings ("ไม่ได้ใช้") int [] b2 = ใหม่ int [n]; lmax.lmax (a, b1); ar = reverse.reverse (a); lmax.lmax (AR, B2); // แก้ปัญหาที่ยาวที่สุดของอาร์เรย์ผกผัน b2 = reverse.reverse (b2); // ผกผันต่อมาที่ยาวที่สุดของอาร์เรย์ผกผันเพื่อเพิ่มความสอดคล้องที่สอดคล้องกับลำดับที่ยาวที่สุดของอาร์เรย์ดั้งเดิม RE = result.result (b1, b2); System.out.print (RE); }} <br> <br> <br> <br> ผลการเรียน {ผลลัพธ์ int คงที่สาธารณะ (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]; } array.sort (c); สูงสุด = c [c.length-1] -1; // บุคคลที่เกี่ยวข้องกับการเพิ่มที่ยาวนานที่สุดและลบการส่งคืน A.Length-Max ซ้ำแล้วซ้ำอีก -ข้างต้นเป็นเนื้อหาทั้งหมดของปัญหาการใช้ Java เพื่อใช้อัลกอริทึม LIS และการก่อตัว ฉันหวังว่ามันจะเป็นประโยชน์กับทุกคนและสนับสนุน wulin.com เพิ่มเติม ~