หาผลรวม sub-array สูงสุดด้วยอัลกอริทึม Divide and Conquer ใน C++

บทนำ

กำหนดรายการข้อมูลที่มีค่าบวกและลบ ต้องการหาผลรวมของ sub-array (ช่วงต่อเนื่อง) ที่มีผลรวมมากที่สุด

ตัวอย่าง: {-2, -5, 6, -2, -3, 1, 5, -6} → ผลรวมสูงสุด = 7 (จาก sub-array {6, -2, -3, 1, 5})

วิธี Divide and Conquer

1. แบ่งอาร์เรย์ออกเป็นสองส่วน
2. หาค่าสูงสุดของ 3 กรณี:
   • ผลรวม sub-array สูงสุดของครึ่งซ้าย
   • ผลรวม sub-array สูงสุดของครึ่งขวา
   • ผลรวม sub-array สูงสุดที่ข้ามจุดกึ่งกลาง (crossing midpoint)

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

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

int max(int a, int b) { return (a > b) ? a : b; }
int max(int a, int b, int c) { return max(max(a, b), c); }

int getMaxCrossingSum(int arr[], int l, int m, int h) {
    int sum = 0;
    int left = INT_MIN;
    for (int i = m; i >= l; i--) {
        sum += arr[i];
        if (sum > left) left = sum;
    }
    sum = 0;
    int right = INT_MIN;
    for (int i = m + 1; i <= h; i++) {
        sum += arr[i];
        if (sum > right) right = sum;
    }
    return left + right;
}

int maxSubArraySum(int arr[], int low, int high) {
    if (low == high) return arr[low];
    int mid = (low + high) / 2;
    return max(maxSubArraySum(arr, low, mid),
               maxSubArraySum(arr, mid + 1, high),
               getMaxCrossingSum(arr, low, mid, high));
}

int main() {
    int arr[] = {-2, -5, 6, -2, -3, 1, 5, -6};
    int n = sizeof(arr) / sizeof(arr[0]);
    int max_sum = maxSubArraySum(arr, 0, n - 1);
    printf("Maximum contiguous sum is %d", max_sum);
    return 0;
}

ผลลัพธ์

Maximum contiguous sum is 7