หาผลรวมสูงสุดของ Subarray ที่ติดกัน (Kadane's Algorithm)

กำหนดอาร์เรย์จำนวนเต็ม ต้องการหาผลรวมของ subarray ที่ติดกัน (contiguous) ซึ่งมีค่ามากที่สุด

Kadane's Algorithm เป็นวิธี Dynamic Programming ที่มีประสิทธิภาพ เก็บค่า "ผลรวมสูงสุดที่ลงท้าย tạiตำแหน่งปัจจุบัน" ไปเรื่อยๆ

ตัวอย่าง Input และ Output

Input: {-2, -3, 4, -1, -2, 1, 5, -3}
Output: Maximum Sum of the Subarray is: 7
(Subarray: {4, -1, -2, 1, 5})

อัลกอริทึม Kadane's Algorithm

ฟังก์ชัน maxSum(array, n)

ขั้นตอน:

1. tempMax = array[0] (คำตอบสุดท้าย)
2. currentMax = tempMax (ผลรวมสูงสุดที่ลงท้ายที่ตำแหน่งปัจจุบัน)
3. สำหรับ i = 1 ถึง n-1:
   • currentMax = max(array[i], currentMax + array[i])
   • tempMax = max(tempMax, currentMax)
4. คืนค่า tempMax

เหตุผล:

ที่ตำแหน่ง i เรามี 2 ทางเลือก: เริ่ม subarray ใหม่ที่ i (array[i]) หรือต่อยอดจาก subarray ก่อนหน้า (currentMax + array[i]) เลือกตัวที่ใหญ่กว่า

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

#include <iostream>
#include <algorithm>
using namespace std;

int maxSum(int arr[], int n) {
    int tempMax = arr[0];
    int currentMax = tempMax;

    for (int i = 1; i < n; i++) {
        currentMax = max(arr[i], currentMax + arr[i]);
        tempMax = max(tempMax, currentMax);
    }
    return tempMax;
}

int main() {
    int arr[] = {-2, -3, 4, -1, -2, 1, 5, -3};
    int n = 8;
    cout << "Maximum Sum of the Sub-array is: " << maxSum(arr, n);
    return 0;
}

Output

Maximum Sum of the Sub-array is: 7

ความซับซ้อน

• Time: O(n) - ผ่านอาร์เรย์เพียง 1 ครั้ง
• Space: O(1) - ใช้ตัวแปรคงที่

ขยาย: หาตำแหน่งเริ่ม-จบของ Subarray

เพิ่มตัวแปร start, end, tempStart เพื่อติดตาม index