maxsubarr.cpp

#include <iostream>
using namespace std;

// Function to find the maximum sum of subarray crossing the midpoint
int maxCrossingSum(int arr[], int left, int mid, int right) {
    int leftSum = -1000000; // Manually set a very small value instead of INT_MIN
    int rightSum = -1000000;
    int sum = 0;

    // Find maximum sum in the left half
    for (int i = mid; i >= left; i--) {
        sum += arr[i];
        if (sum > leftSum) {
            leftSum = sum;
        }
    }

    sum = 0;
    // Find maximum sum in the right half
    for (int i = mid + 1; i <= right; i++) {
        sum += arr[i];
        if (sum > rightSum) {
            rightSum = sum;
        }
    }

    // Return sum of left, right, and crossing subarray
    return leftSum + rightSum;
}

// Divide and conquer function to find the maximum subarray sum
int maxSubArraySum(int arr[], int left, int right) {
    // Base case: if there is only one element
    if (left == right) {
        return arr[left];
    }

    // Find the middle point
    int mid = (left + right) / 2;

    // Recursively find the maximum subarray sum for the left and right halves
    int leftSum = maxSubArraySum(arr, left, mid);
    int rightSum = maxSubArraySum(arr, mid + 1, right);

    // Find the maximum sum of the subarray that crosses the midpoint
    int crossSum = maxCrossingSum(arr, left, mid, right);

    // Return the maximum of the three
    return max(max(leftSum, rightSum), crossSum);
}

int main() {
    int n;

    // Input the size of the array
    cout << "Enter the size of the array: ";
    cin >> n;

    int arr[n];
    
    // Input the elements of the array
    cout << "Enter the elements of the array: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // Call the divide and conquer function to find the maximum subarray sum
    int result = maxSubArraySum(arr, 0, n - 1);
    
    cout << "The maximum subarray sum is: " << result << endl;

    return 0;
}