Kadane's Algorithm ใน C++: หา Maximum Subarray Sum

Kadane's Algorithm หา Maximum Sum ของ Contiguous Subarray ใน O(N) Time, O(1) Space วิธีคิดคือ Dynamic Programming แบบเก็บเฉพาะ State ที่จำเป็น

Algorithm Logic

ที่ Index i เรามี 2 ทางเลือก:

1. เริ่ม Subarray ใหม่ที่ i: arr[i]
2. ต่อยอด Subarray ก่อนหน้า: currentMax + arr[i]

เลือก Max ของทั้งสอง → currentMax = max(arr[i], currentMax + arr[i])

อัปเดต Global Max: globalMax = max(globalMax, currentMax)

โค้ด C++

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

// Return pair: {maxSum, {startIdx, endIdx}}
pair> kadane(const vector& arr) {
    long long maxSum = LLONG_MIN;
    long long currSum = 0;
    int start = 0, end = 0, tempStart = 0;
    
    for (int i = 0; i < arr.size(); i++) {
        if (currSum + arr[i] < arr[i]) {
            currSum = arr[i];
            tempStart = i;
        } else {
            currSum += arr[i];
        }
        
        if (currSum > maxSum) {
            maxSum = currSum;
            start = tempStart;
            end = i;
        }
    }
    return {maxSum, {start, end}};
}

int main() {
    // Example from article
    vector arr = {-1, -2, -3, -4, -5, 6, 7};
    
    auto result = kadane(arr);
    cout << "Array: ";
    for (int x : arr) cout << x << " ";
    cout << "\nMaximum Subarray Sum: " << result.first;
    cout << "\nSubarray indices: [" << result.second.first << ", " << result.second.second << "]";
    cout << "\nSubarray: ";
    for (int i = result.second.first; i <= result.second.second; i++)
        cout << arr[i] << " ";
    cout << '\n';
    
    return 0;
}

ผลลัพธ์

Array: -1 -2 -3 -4 -5 6 7
Maximum Subarray Sum: 13
Subarray indices: [5, 6]
Subarray: 6 7

Edge Cases

Variations

1. Maximum Subarray Product

// Track both max and min (because negative * negative = positive)
long long maxProduct(vector& nums) {
    long long maxProd = nums[0], minProd = nums[0], result = nums[0];
    for (int i = 1; i < nums.size(); i++) {
        if (nums[i] < 0) swap(maxProd, minProd);
        maxProd = max((long long)nums[i], maxProd * nums[i]);
        minProd = min((long long)nums[i], minProd * nums[i]);
        result = max(result, maxProd);
    }
    return result;
}

2. Maximum Circular Subarray Sum

// Case 1: Normal Kadane
// Case 2: Total Sum - Min Subarray Sum (wrap around)
// Answer = max(case1, case2) unless all negative
long long maxCircularSubarraySum(vector& arr) {
    long long maxKadane = kadane(arr).first;
    long long total = accumulate(arr.begin(), arr.end(), 0LL);
    
    // Invert and find min subarray (Kadane for min)
    vector inverted(arr.size());
    transform(arr.begin(), arr.end(), inverted.begin(), [](int x){ return -x; });
    long long minKadane = -kadane(inverted).first;
    
    if (total == minKadane) return maxKadane; // All negative
    return max(maxKadane, total - minKadane);
}

3. Maximum Subarray Sum with Length Constraint

ใช้ Sliding Window + Deque หรือ Prefix Sum + Monotonic Queue

Complexity

• Time: O(N) - Single Pass
• Space: O(1) - เก็บแค่ Variables ชंदตัว

ประวัติศาสตร์

Jay Kadane พัฒนาในปี 1984 ที่ Carnegie Mellon University เป็นหนึ่งใน Dynamic Programming Problems ที่มี名声高い ที่สุด

C++ Program: Longest Common Subsequence (LCS) ของหลาย Sequences

C++ Program: Implement Affine Cipher (Affine Cipher)