LeetCode #53 Maximum Subarray: Kadane จากคำถามว่าจะต่อหรือเริ่มใหม่

โจทย์ maximum-subarray ให้ array ที่มีอย่างน้อยหนึ่งสมาชิก ต้องหาผลรวมสูงสุดของช่วงต่อเนื่องที่ไม่ว่าง คำว่า “ไม่ว่าง” ทำให้ input ติดลบทั้งหมดตอบสมาชิกที่ติดลบน้อยที่สุด ไม่ใช่ศูนย์

วิธีที่ 1: ขยายทุกจุดเริ่ม

เลือกซ้ายทุกตำแหน่งแล้วสะสมผลรวมเมื่อขยับขวา เวลา O(n²), พื้นที่ O(1) ดีกว่าคำนวณ sum ใหม่ทุกคู่ที่กลายเป็น O(n³) และเหมาะเป็น oracle สำหรับทดสอบข้อมูลเล็ก

วิธีที่ 2: prefix sum กับ minimum prefix

ผลรวมช่วง [i, j) เท่ากับ prefix[j] ลบ prefix[i] ดังนั้นเดินทีละจุด เก็บ prefix ต่ำสุดก่อนหน้าและผลต่างสูงสุดได้ใน O(n)/O(1) วิธีนี้เชื่อมไปโจทย์ prefix อื่นได้ดี แต่ต้องระวังลำดับอัปเดตเพื่อไม่เลือกช่วงว่าง

วิธีที่ 3: Kadane (แนะนำหลัก)

ที่แต่ละค่า มีเพียงสองทาง: ต่อช่วงที่จบก่อนหน้า หรือเริ่มช่วงใหม่ที่ค่าปัจจุบัน เก็บ ending_here = max(value, ending_here + value) และ best เวลา O(n), พื้นที่ O(1) Invariant คือ ending_here เป็นผลรวมสูงสุดของช่วงที่ต้องจบตรงตำแหน่งนี้

วิธีที่ 4: divide-and-conquer

คำตอบอยู่ซ้าย ขวา หรือข้ามกึ่งกลาง รวม prefix/suffix ที่ดีที่สุดแล้ว recurse ได้ O(n log n) มีคุณค่าด้านการสอนและต่อยอดเป็น segment tree แต่ซับซ้อนกว่า Kadane สำหรับคำถามครั้งเดียว

import unittest


def maximum_subarray(nums):
    if not nums:
        raise ValueError("nums must be non-empty")
    ending_here = best = nums[0]
    for value in nums[1:]:
        ending_here = max(value, ending_here + value)
        best = max(best, ending_here)
    return best


def maximum_subarray_bruteforce(nums):
    if not nums:
        raise ValueError("nums must be non-empty")
    best = nums[0]
    for left in range(len(nums)):
        total = 0
        for right in range(left, len(nums)):
            total += nums[right]
            best = max(best, total)
    return best


class MaximumSubarrayTests(unittest.TestCase):
    def test_examples_and_all_negative(self):
        cases = [
            ([-2, 1, -3, 4, -1, 2, 1, -5, 4], 6),
            ([-8, -3, -6], -3),
            ([5], 5),
            ([0, 0], 0),
        ]
        for nums, expected in cases:
            with self.subTest(nums=nums):
                self.assertEqual(maximum_subarray(nums), expected)
                self.assertEqual(maximum_subarray(nums), maximum_subarray_bruteforce(nums))

    def test_empty_input_is_rejected(self):
        with self.assertRaises(ValueError):
            maximum_subarray([])


if __name__ == "__main__":
    unittest.main()

เลือกตามโจทย์

เป้าหมาย	วิธี
อธิบายจากนิยาม/สร้าง test oracle	O(n²)
เชื่อมแนวคิด prefix sum	minimum prefix
คำตอบมาตรฐานและ production scan	Kadane
ต้องตอบ query หลายช่วงภายหลัง	divide-and-conquer/segment tree

ถ้าต้องคืน indices ให้เก็บจุดเริ่ม candidate เมื่อเลือก value แทน ending_here + value และบันทึกขอบเมื่อ best ดีขึ้น ต้องกำหนด tie-breaking ว่าเอาช่วงสั้นสุดหรือซ้ายสุด มิฉะนั้น implementation ที่ผลรวมเท่ากันอาจคืนคนละช่วง

Recap

Kadane คือ default เพราะ O(n)/O(1) และพิสูจน์ด้วย state “ช่วงที่ต้องจบตรงนี้” อย่าตั้ง best เป็นศูนย์เมื่อโจทย์บังคับช่วงไม่ว่าง และใช้ brute force เทียบผลบนอาร์เรย์สุ่มสั้นเพื่อจับ edge case ครับ