โปรแกรม Python แก้ปัญหา Maximum Subarray ด้วย Kadane's Algorithm

Kadane's Algorithm หา Subarray ที่มีผลรวมมากที่สุดใน O(n) โดยเก็บ running sum และ max sum ที่เจอมา

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

def max_subarray(arr):
    max_ending_here = max_so_far = arr[0]
    start = end = temp_start = 0
    
    for i in range(1, len(arr)):
        if max_ending_here + arr[i] > arr[i]:
            max_ending_here += arr[i]
        else:
            max_ending_here = arr[i]
            temp_start = i
        
        if max_ending_here > max_so_far:
            max_so_far = max_ending_here
            start = temp_start
            end = i
    
    return start, end, max_so_far

nums = list(map(int, input("Enter numbers: ").split()))
start, end, max_sum = max_subarray(nums)
print(f"Max subarray: index {start} to {end}, sum = {max_sum}")

ผลลัพธ์

Enter numbers: 2 5 7 12 6 8
Max subarray: index 0 to 5, sum = 40

คำอธิบาย

• max_ending_here: ผลรวมสูงสุดของ subarray ที่จบที่ index ปัจจุบัน

• max_so_far: ผลรวมสูงสุดที่เจอมาจนถึงตอนนี้

• ถ้าเพิ่ม arr[i] ทำให้ดีกว่าเริ่มใหม่ที่ arr[i] ให้ต่อยอด ไม่อย่างนั้น เริ่มใหม่

• ติดตาม start/end index ด้วย temp_start

• Time Complexity: O(n), Space: O(1)