Find sum of contiguous subarray within one-dimensional array

Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of numbers which has the largest sum.

Examples:

Input :  {-2, -3, 4, -1, -2, 1, 5, -3}
Output : 7
The subarray {4,-1,-2,1,5} gives the maximum sum among all other possible sub-arrays.

Algorithmic Paradigm: Divide And Conquer

To apply Divide and Conquer technique, we first need to figure out how to divide the input. Dividing in the middle often gives the best bounds as it reduces the problem instances of several subproblems

• Case 1: It can be completely in the left half.
• Case 2: It can be completely in the right half.
• Case 3: It begins in left half and ends in right half.

Implementation in C++

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

// Function to calculate maximum contiguous subsequence that begins in the left half and ends in the right half.
int combinedSum(int *arr, int low, int mid, int high) {
    // Calculate left max subarray
    int sum = 0, leftSum = INT_MIN;
    for (int i = mid; i >= low; i--) {
        sum += arr[i];
        if (sum > leftSum)
            leftSum = sum;
    }
    sum = 0;
    int rightSum = INT_MIN;
    // Calculate right max subarray
    for (int i = mid + 1; i <= high; i++) {
        sum += arr[i];
        if (sum > rightSum)
            rightSum = sum;
    }
    return leftSum + rightSum;
}

// Function to calculate the maximum possible sum
int maxSubArraySumUtil(int *arr, int low, int high) {
    // Base case: one element in array
    if (low == high)
        return arr[low];
    else {
        int mid = (low + high) / 2;
        // Recursive Subproblems
        int leftSum = maxSubArraySumUtil(arr, low, mid);
        int rightSum = maxSubArraySumUtil(arr, mid + 1, high);
        // Crossing Subproblem
        int crossSum = combinedSum(arr, low, mid, high);
        // Case 1: Max subarray is in the left array
        if (leftSum >= rightSum && leftSum >= crossSum)
            return leftSum;
        // Case 2: Max subarray is in the right array
        else if (rightSum >= leftSum && rightSum >= crossSum)
            return rightSum;
        // Case 3: Max subarray is in the array crossing midpoints
        else
            return crossSum;
    }
    return 0;
}

int maxSubArraySum(int a[], int size) {
    int low = 0;
    return maxSubArraySumUtil(a, low, size - 1);
}

/*Driver program to test maxSubArraySum*/
int main() {
    int a[] = {-1, -2, -3, -4, 5, 6, 7};
    int n = sizeof(a) / sizeof(a[0]);
    int max_sum = maxSubArraySum(a, n);
    cout << "Maximum possible sum is: " << max_sum << endl;
    return 0;
}

Output:

Maximum possible sum is: 18

The recurrence relation is:

T(1) = 1
T(n) = 2T(n/2) + n

Using D&C Master Theorem, we get the time complexity as T(n)=O(nlogn).