#include <stdio.h>
#include <limits.h>
// Utility function to find maximum of two numbers
int max(int x, int y) {
return (x > y) ? x : y;
}
// Function to find maximum subarray sum using divide and conquer
int maximum_sum(int A[], int low, int high)
{
// If array contains only one element
if (high == low)
return A[low];
// Find middle element of the array
int mid = (low + high) / 2;
// Find maximum subarray sum for the left subarray
// including the middle element
int left_max = INT_MIN;
int sum = 0;
for (int i = mid; i >= low; i--)
{
sum += A[i];
if (sum > left_max)
left_max = sum;
}
// Find maximum subarray sum for the right subarray
// excluding the middle element
int right_max = INT_MIN;
sum = 0; // reset sum to 0
for (int i = mid + 1; i <= high; i++)
{
sum += A[i];
if (sum > right_max)
right_max = sum;
}
// Recursively find the maximum subarray sum for left subarray
// and right subarray and take maximum
int max_left_right = max(maximum_sum(A, low, mid),
maximum_sum(A, mid + 1, high));
// return maximum of the three
return max(max_left_right, left_max + right_max);
}
// Maximum Sum Subarray using Divide & Conquer
int main(void)
{
int arr[] = { 2, -4, 1, 9, -6, 7, -3 };
int n = sizeof(arr) / sizeof(arr[0]);
printf("The maximum sum of the subarray is %d", maximum_sum
(arr
, 0, n
- 1));
return 0;
}
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxsaW1pdHMuaD4KCi8vIFV0aWxpdHkgZnVuY3Rpb24gdG8gZmluZCBtYXhpbXVtIG9mIHR3byBudW1iZXJzCmludCBtYXgoaW50IHgsIGludCB5KSB7CiAgICByZXR1cm4gKHggPiB5KSA/IHggOiB5Owp9CgovLyBGdW5jdGlvbiB0byBmaW5kIG1heGltdW0gc3ViYXJyYXkgc3VtIHVzaW5nIGRpdmlkZSBhbmQgY29ucXVlcgppbnQgbWF4aW11bV9zdW0oaW50IEFbXSwgaW50IGxvdywgaW50IGhpZ2gpCnsKICAgIC8vIElmIGFycmF5IGNvbnRhaW5zIG9ubHkgb25lIGVsZW1lbnQKICAgIGlmIChoaWdoID09IGxvdykKICAgICAgICByZXR1cm4gQVtsb3ddOwoKICAgIC8vIEZpbmQgbWlkZGxlIGVsZW1lbnQgb2YgdGhlIGFycmF5CiAgICBpbnQgbWlkID0gKGxvdyArIGhpZ2gpIC8gMjsKCiAgICAvLyBGaW5kIG1heGltdW0gc3ViYXJyYXkgc3VtIGZvciB0aGUgbGVmdCBzdWJhcnJheQogICAgLy8gaW5jbHVkaW5nIHRoZSBtaWRkbGUgZWxlbWVudAogICAgaW50IGxlZnRfbWF4ID0gSU5UX01JTjsKICAgIGludCBzdW0gPSAwOwogICAgZm9yIChpbnQgaSA9IG1pZDsgaSA+PSBsb3c7IGktLSkKICAgIHsKICAgICAgICBzdW0gKz0gQVtpXTsKICAgICAgICBpZiAoc3VtID4gbGVmdF9tYXgpCiAgICAgICAgICAgIGxlZnRfbWF4ID0gc3VtOwogICAgfQoKICAgIC8vIEZpbmQgbWF4aW11bSBzdWJhcnJheSBzdW0gZm9yIHRoZSByaWdodCBzdWJhcnJheQogICAgLy8gZXhjbHVkaW5nIHRoZSBtaWRkbGUgZWxlbWVudAogICAgaW50IHJpZ2h0X21heCA9IElOVF9NSU47CiAgICBzdW0gPSAwOyAgICAvLyByZXNldCBzdW0gdG8gMAogICAgZm9yIChpbnQgaSA9IG1pZCArIDE7IGkgPD0gaGlnaDsgaSsrKQogICAgewogICAgICAgIHN1bSArPSBBW2ldOwogICAgICAgIGlmIChzdW0gPiByaWdodF9tYXgpCiAgICAgICAgICAgIHJpZ2h0X21heCA9IHN1bTsKICAgIH0KCiAgICAvLyBSZWN1cnNpdmVseSBmaW5kIHRoZSBtYXhpbXVtIHN1YmFycmF5IHN1bSBmb3IgbGVmdCBzdWJhcnJheQogICAgLy8gYW5kIHJpZ2h0IHN1YmFycmF5IGFuZCB0YWtlIG1heGltdW0KICAgIGludCBtYXhfbGVmdF9yaWdodCA9IG1heChtYXhpbXVtX3N1bShBLCBsb3csIG1pZCksCiAgICAgICAgICAgICAgICAgICAgICAgICAgICBtYXhpbXVtX3N1bShBLCBtaWQgKyAxLCBoaWdoKSk7CgogICAgLy8gcmV0dXJuIG1heGltdW0gb2YgdGhlIHRocmVlCiAgICByZXR1cm4gbWF4KG1heF9sZWZ0X3JpZ2h0LCBsZWZ0X21heCArIHJpZ2h0X21heCk7Cn0KCi8vIE1heGltdW0gU3VtIFN1YmFycmF5IHVzaW5nIERpdmlkZSAmIENvbnF1ZXIKaW50IG1haW4odm9pZCkKewogICAgaW50IGFycltdID0geyAyLCAtNCwgMSwgOSwgLTYsIDcsIC0zIH07CiAgICBpbnQgbiA9IHNpemVvZihhcnIpIC8gc2l6ZW9mKGFyclswXSk7CgogICAgcHJpbnRmKCJUaGUgbWF4aW11bSBzdW0gb2YgdGhlIHN1YmFycmF5IGlzICVkIiwgbWF4aW11bV9zdW0oYXJyLCAwLCBuIC0gMSkpOwoKICAgIHJldHVybiAwOwp9