Maximum Sum SubArray ด้วย Divide and Conquer ใน C++

สมมติมี List ข้อมูล Positive และ Negative ต้องการหา Sum ของ Contiguous Subarray ที่มี Sum มากที่สุด ตัวอย่าง {-2, -5, 6, -2, -3, 1, 5, -6} Max Subarray Sum = 7 จาก {6, -2, -3, 1, 5}

แก้ด้วย Divide and Conquer:

1. แบ่ง Array เป็น 2 ส่วน
2. หา Max ของ 3 ค่า:
   • Max Subarray Sum ของ Left Subarray
   • Max Subarray Sum ของ Right Subarray
   • Max Subarray Sum ที่ข้าม Midpoint

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

#include <iostream>
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 = sum + arr[i];
        if (sum > left)
            left = sum;
    }
    sum = 0;
    int right = INT_MIN;
    for (int i = m+1; i <= h; i++) {
        sum = 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);
}

ผลลัพธ์

Valid String