Maximum Subarray ด้วยอัลกอริทึม Kadane
แต่ละตำแหน่งตัดสินใจว่าจะต่อช่วงเดิมหรือเริ่มใหม่
Maximum Subarray ด้วยอัลกอริทึม Kadane คืออะไร?
แต่ละตำแหน่งตัดสินใจว่าจะต่อช่วงเดิมหรือเริ่มใหม่
หาช่วงต่อเนื่องที่มีผลรวมมากที่สุด
ควรใช้เมื่อใด?
- ทำความเข้าใจอัลกอริทึมและโครงสร้างข้อมูล
- สังเกตแต่ละขั้นตอนและกรณีขอบ
- เปรียบเทียบเวลาและหน่วยความจำ
โค้ดตัวอย่าง
main.py
def maximum_subarray_sum(values):
current = best = values[0]
for value in values[1:]:
current = max(value, current + value)
best = max(best, current)
return best
print(maximum_subarray_sum([-2, 1, -3, 4, -1, 2, 1, -5, 4]))ผลลัพธ์ที่คาดหวัง
6หลักการทำงาน
วนเพียงครั้งเดียว จึงใช้เวลา O(n) และหน่วยความจำ O(1)
เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python
แบบฝึกหัด
ลองเปลี่ยน input และทดสอบกรณีขอบก่อนใช้ชุดข้อมูลที่ใหญ่ขึ้น
- ทดสอบ input ว่าง หนึ่งสมาชิก และค่าซ้ำ
- แสดงสถานะหลังแต่ละขั้นตอน
- เปรียบเทียบประสิทธิภาพกับวิธีอื่น