CodeUtility
ใช้ชีวิตนักพัฒนาให้ง่ายขึ้นไปอีก!
อัลกอริทึม Python

Maximum Subarray Sum with Kadane's Algorithm in Python

Find the run of numbers with the largest sum in one pass, even when the list has negative values.

  • ระดับกลาง
  • อ่าน 2 นาที
  • ตัวอย่างที่รันได้ 1 ตัวอย่าง
สิ่งที่คุณจะได้เรียนรู้
  • The best sum ending at each position
  • Starting fresh when the running sum hurts
  • O(n) time and O(1) memory
รันในคอมไพเลอร์ Python →
[-2, 1, -3, 4, -1, 2, 1, -5, 4]
-2
1
-3
4
-1
2
1
-5
4
4 - 1 + 2 + 1 = 6 is the largest sum of any contiguous run.

Extend the run or start again

โจทย์ช่วงย่อยที่ผลรวมมากที่สุด (maximum subarray) คือการหาช่วงสมาชิกที่ติดกันซึ่งมีผลรวมมากที่สุดในลิสต์ที่มีทั้งเลขบวกและเลขลบ อัลกอริทึมของ Kadane แก้โจทย์นี้ได้อย่างมีประสิทธิภาพ โดยจำผลรวมที่ดีที่สุดของช่วงที่จบที่ตำแหน่งปัจจุบัน

ประเด็นสำคัญ

  1. current = max(value, current + value): keep the run only if it helps.
  2. best = max(best, current) remembers the best run so far.
  3. Start both from the first value so all-negative lists work.

ใช้เมื่อไร?

  • ฝึกคิดอย่างเป็นระบบและเข้าใจการทำงานของอัลกอริทึมทีละขั้น
  • เลือกวิธีที่เหมาะสมเมื่อต้องจัดการข้อมูลจำนวนมากหรือทำให้โปรแกรมเร็วขึ้น
  • เตรียมตัวสำหรับการสอบ แบบฝึกหัด และการสัมภาษณ์งานเขียนโปรแกรม

โค้ดตัวอย่าง

รันโค้ด →
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]))
สร้างปุ่ม Run สำหรับตัวอย่างนี้

ผลลัพธ์จากการรัน

6

อธิบายโค้ด

สำหรับแต่ละสมาชิก ตัวแปร current เลือกระหว่างสองทาง คือเริ่มช่วงใหม่ที่สมาชิกนี้ หรือต่อช่วงเดิมด้วย current + value ตัวแปร best เก็บผลรวมที่มากที่สุดที่เคยเจอ จากข้อมูลตัวอย่าง ช่วง [4, -1, 2, 1] ให้ผลรวมมากที่สุดคือ 6 อัลกอริทึมทำงานใน O(n) และใช้หน่วยความจำเพียง O(1)

เปลี่ยนค่าและรันโปรแกรมด้วย คอมไพเลอร์ Python ออนไลน์ของ CodeUtility โดยไม่ต้องติดตั้ง Python

แบบฝึกหัดเพิ่มเติม

ลองแก้โค้ดตามคำแนะนำด้านล่าง การเปลี่ยนโค้ดแล้วดูผลลัพธ์จะช่วยให้เข้าใจบทเรียนได้ดีกว่าการอ่านอย่างเดียวมาก

  1. ทดสอบกับลิสต์ว่าง ลิสต์ที่มีสมาชิกตัวเดียว และลิสต์ที่มีค่าซ้ำ
  2. แสดงสถานะหลังแต่ละขั้นเพื่อดูการทำงานของอัลกอริทึม
  3. จับเวลาการทำงานกับข้อมูล 100, 1,000 และ 10,000 ตัว แล้วเทียบกับวิธีอื่น
รันในคอมไพเลอร์ Python →

ฝึกด้วยโจทย์

ใช้สิ่งที่เรียนในบทนี้แก้ปัญหาจริง ทุกโจทย์รันในเบราว์เซอร์ พร้อมการทดสอบทันทีและรีวิวจาก AI

โจทย์ทั้งหมด