Maximum_Subarray_Problem [DivideAndConquer]

//////////////////////////////////////////////////////////////
//      Author: Shakib Haris                                //
//      Problem: Maximum Subarray Problem                   //
//      Solution: Divide and Conquer // O(n lg n)           //
//      Input: The Change(s) of Price(s), not the Price(s)  //
//      Output: Maximum Subarray                            //
//////////////////////////////////////////////////////////////

#include <iostream>
#include <climits>
#define SIZE 10

using namespace std;


void findMaxCrossingSubarray(int A[], int lo, int mid, int hi, int &maxLeft, int &maxRight, int &crossSum) {
    int leftSum = INT_MIN;
    int Sum = 0;
    for (int i = mid; i >= lo; i--) {
        Sum += A[i];
        if (Sum > leftSum) {
            leftSum = Sum;
            maxLeft = i;
        }
    }

    int rightSum = INT_MIN;
    Sum = 0;
    for (int i = mid + 1; i <= hi; i++) {
        Sum += A[i];
        if (Sum > rightSum) {
            rightSum = Sum;
            maxRight = i;
        }
    }

    crossSum = leftSum + rightSum;
    return;
}


void findMaxSubarray(int A[], int lo, int hi, int &maxLo, int &maxHi, int &maxSum) {
    if (lo == hi) {
        maxLo = lo;
        maxHi = hi;
        maxSum = A[lo];
        return;
    }
    else {
        int mid = (lo + hi) / 2;
        int leftLo, leftHi, leftSum, rightLo, rightHi, rightSum, crossLo, crossHi, crossSum;
        findMaxSubarray(A, lo, mid, leftLo, leftHi, leftSum);
        findMaxSubarray(A, mid + 1, hi, rightLo, rightHi, rightSum);
        findMaxCrossingSubarray(A, lo, mid, hi, crossLo, crossHi, crossSum);

        if (leftSum >= rightSum && leftSum >= crossSum) {
            maxLo = leftLo;
            maxHi = leftHi;
            maxSum = leftSum;
        }
        else if (rightSum >= leftSum && rightSum >= crossSum) {
            maxLo = rightLo;
            maxHi = rightHi;
            maxSum = rightSum;
        }
        else {
            maxLo = crossLo;
            maxHi = crossHi;
            maxSum = crossSum;
        }
        return;
    }
}


void display (int A[], int lo, int hi) {
    for (int i = lo; i <= hi; i++)
        cout << A[i] << " ";
    cout << endl << endl;
}


int main() {
    int A[SIZE];

    for (int i = 0; i < SIZE; i++)
        cin >> A[i];

    cout << "Original Array: ";
    display(A, 0, SIZE - 1);

    int lo, hi, Sum;

    findMaxSubarray(A, 0, SIZE - 1, lo, hi, Sum);

    cout << "Max Sum: " << Sum << endl;
    cout << "Sub-array: ";
    display(A, lo, hi);

    return 0;
}