MSA_Full

#include <iostream>
#include <iomanip>
#include <fstream>
#include <ctime>
#include <cstdlib>
#include <climits>
#define SIZE 100000

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 kadanes (int A[], int N, int &start, int &end, int &maxSoFar) {
    int maxEndingHere = A[0];
    maxSoFar = A[0];
    int tStart = start = end = 0;

    for (int i = 1; i < N; i++) {
        maxEndingHere += A[i];

        if (maxEndingHere < A[i]) {
            maxEndingHere = A[i];
            tStart = i;
        }
        if (maxSoFar < maxEndingHere) {
            maxSoFar = maxEndingHere;
            start = tStart;
            end = i;
        }
    }
    return;
}



void bruteForce(int A[], int N, int &start, int &end, int &max) {
    max = INT_MIN;
    int sum;
    for (int i = 0; i < N; i++) {
        sum = 0;
        for (int j = i; j < N; j++) {
            sum += A[j];
            if (sum > max) {
                start = i;
                end = j;
                max = sum;
            }
        }
    }
}



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];

    int lo, hi, Sum;
    long long start, end;

    srand(time(NULL));
    for (int i = 0; i < SIZE; i++)
        A[i] = rand() % 2 ? rand() % 100 : rand() % 100 * -1;


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

    //for (int i = 0; i < SIZE; i++)
    //    cout << A[i] << " ";
    //cout << endl << endl;

    ofstream out;
    out.open("MSA-DATA.txt", ios::app);

    cout << "SIZE: " << SIZE << endl;
    out << "SIZE: " << SIZE << endl;

    start = clock();
    findMaxSubarray(A, 0, SIZE - 1, lo, hi, Sum);
    end = clock();
    cout << "Max Sum: " << Sum << endl;
    cout << "Sub-array: [" << lo << "..." << hi << "]" << endl;;
    out << "Recursive: "  << fixed << setprecision(4) << (end - start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl;
    cout << "Recursive: "  << fixed << setprecision(4) << (end - start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl << endl << endl;


    start = clock();
    kadanes(A, SIZE, lo, hi, Sum);
    end = clock();
    cout << "Max Sum: " << Sum << endl;
    cout << "Sub-array: [" << lo << "..." << hi << "]" << endl;;
    out << "Kadane's: "  << fixed << setprecision(4) << (end - start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl;
    cout << "Kadane's: "  << fixed << setprecision(4) << (end - start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl << endl << endl;


    start = clock();
    bruteForce(A, SIZE, lo, hi, Sum);
    end = clock();
    cout << "Max Sum: " << Sum << endl;
    cout << "Sub-array: [" << lo << "..." << hi << "]" << endl;;
    out << "Brute-Force: "  << fixed << setprecision(4) << (end - start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl << endl << endl;
    cout << "Brute-Force: "  << fixed << setprecision(4) << (end - start) * 1.0 / CLOCKS_PER_SEC << " Seconds" << endl << endl << endl;



    //cout << "Max Sum: " << Sum << endl;
    //cout << "Sub-array: [" << lo << "..." << hi << "] = ";
    //display(A, lo, hi);

    return 0;
}