ลำดับย่อยที่เพิ่มขึ้นยาวที่สุด
DP O(n^2) แล้วต่อด้วยเทคนิค O(n log n)
ลำดับย่อยที่เพิ่มขึ้นยาวที่สุด เป็นบทเรียน Competitive Programming Academy ฟรีบน CoddyKit นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Competitive Programming Academy และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
LIS คืออะไร
ลำดับย่อย จะรักษาลำดับเดิมไว้ แต่สามารถข้ามสมาชิกได้ ลำดับย่อยแบบเพิ่มขึ้นที่ยาวที่สุดคือลำดับย่อยที่เพิ่มขึ้นอย่างเคร่งครัดและมีความยาวมากที่สุด
a = [3, 1, 4, 1, 5, 9, 2]ลำดับย่อย ไม่ใช่อาร์เรย์ย่อย
ต่างจากอาร์เรย์ย่อยตรงที่ LIS ไม่จำเป็นต้อง ต่อเนื่องติดกัน คุณสามารถข้ามตัวเลขที่เล็กกว่าเพื่อให้ลำดับเติบโตต่อไปได้
สถานะ DP แบบ O(n^2)
ให้ dp[i] เป็นความยาวของ LIS ที่ สิ้นสุดที่ดัชนี i สมาชิกทุกตัวเป็นลำดับย่อยความยาวหนึ่งได้ด้วยตัวมันเองเป็นอย่างน้อย
dp = [1] * nการเปลี่ยนสถานะแบบ O(n^2)
สำหรับแต่ละ i ให้พิจารณา j ก่อนหน้าทุกค่า หาก a[j] มีค่าน้อยกว่า ก็ขยายลำดับ: dp[i] = max(dp[i], dp[j] + 1)
for i in range(n):
for j in range(i):
if a[j] < a[i]:
dp[i] = max(dp[i], dp[j]+1)อ่านคำตอบจากตาราง
คำตอบคือค่าที่มากที่สุดในตาราง เพราะ LIS สามารถ สิ้นสุดที่ตำแหน่งใดก็ได้ ไม่จำเป็นต้องสิ้นสุดที่ดัชนีสุดท้าย
answer = max(dp)เหตุใด O(n^2) จึงทำให้ได้ TLE
รอบวนซ้ำสองชั้นใช้เวลาในระดับ O(n กำลังสอง) เมื่อ n ใกล้ 100000 จะช้าเกินไปมากและทำให้ได้ผลตัดสิน เกินขีดจำกัดเวลา
แนวคิดแบบ patience
วิธีที่เร็วกว่าจะเก็บรายการ ค่าท้ายที่น้อยที่สุดเท่าที่เป็นไปได้ สำหรับความยาวของลำดับย่อยแต่ละค่า คล้ายการเรียงไพ่แบบ patience
tails = []ใช้การค้นหาแบบแบ่งครึ่งเพื่อจัดวาง
สำหรับตัวเลขแต่ละตัว ให้ค้นหาตำแหน่งที่เหมาะสมในบรรดาค่าท้ายด้วยการค้นหาแบบทวิภาคโดยใช้ bisect_left ทำให้เวลารวมเป็น O(n log n)
from bisect import bisect_leftขยายหรือแทนที่
หากตำแหน่งอยู่นอกท้ายรายการ ให้ใช้ append เพื่อขยาย LIS มิฉะนั้นให้เขียนทับค่าท้ายนั้นด้วยค่าที่น้อยกว่า
i = bisect_left(tails, x)
if i == len(tails):
tails.append(x)
else:
tails[i] = xความยาวอยู่ใน tails
เมื่อสแกนครบแล้ว len(tails) คือความยาวของ LIS ตัวรายการเองไม่จำเป็นต้องเป็นลำดับย่อยจริงเสมอไป มีเพียงความยาวเท่านั้นที่ถูกต้องแน่นอน
answer = len(tails)เพิ่มขึ้นอย่างเคร่งครัดกับไม่ลดลง
สำหรับรูปแบบไม่ลดลง ให้เปลี่ยนไปใช้การค้นหาตำแหน่งทางขวา เพื่อให้ค่าที่เท่ากันสามารถขยายลำดับได้
from bisect import bisect_rightตรวจสอบอย่างรวดเร็ว
วิธีใดค้นหาความยาวของ LIS ได้ใน O(n log n)
ทบทวน: จาก n^2 สู่ n log n
ตอนนี้คุณสามารถแก้ LIS ได้สองวิธี DP แบบ O(n^2) เข้าใจง่าย ส่วนวิธีใช้ค่าท้ายร่วมกับการค้นหาแบบแบ่งครึ่งรองรับข้อมูลนำเข้าขนาดใหญ่และไม่เกินขีดจำกัดเวลา
คำถามที่พบบ่อย
บทเรียน “ลำดับย่อยที่เพิ่มขึ้นยาวที่สุด” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “ลำดับย่อยที่เพิ่มขึ้นยาวที่สุด” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Competitive Programming Academy ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Competitive Programming Academy มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “ลำดับย่อยที่เพิ่มขึ้นยาวที่สุด”
DP O(n^2) แล้วต่อด้วยเทคนิค O(n log n) คุณปฏิบัติ Competitive Programming Academy ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Competitive Programming Academy หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Competitive Programming Academy บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 4 จากทั้งหมด 4 บทเรียน
บทเรียน “ลำดับย่อยที่เพิ่มขึ้นยาวที่สุด” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Competitive Programming Academy นี้ได้ไหม
ได้ บทเรียน Competitive Programming Academy ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- การจดจำผลลัพธ์เทียบกับการทำตาราง
- กำหนดสถานะและการเปลี่ยนสถานะ
- การปีนบันไดและการจัดเหรียญ
- ลำดับย่อยที่เพิ่มขึ้นยาวที่สุด