Maximum_Subarray_Problem [Brute_Force (Iterative)]

//////////////////////////////////////////////////////////////
//      Author: Shakib Haris                                //
//      Problem: Maximum Subarray Problem                   //
//      Solution: Brute-Force Approach // O(n^2)            //
//      Input: The Price(s), not the Change(s) of Prices    //
//      Output: Maximum Subarray                            //
//////////////////////////////////////////////////////////////

#include <bits/stdc++.h>
#define SIZE 5
using namespace std;

void bruteForce(int A[], int lo, int hi, int &start, int &end) {
    int maxDiff = INT_MIN;

    for (int i = lo; i < hi; i++)
        for (int j = i + 1; j <= hi; j++)
            if (A[j] - A[i] > maxDiff) {
                start = i;
                end = j;
                maxDiff = A[j] - A[i];
            }
}


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], start, end;

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

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

    bruteForce(A, 0, SIZE - 1, start, end);

    cout << "Sub-array: ";
    display(A, start, end);

    return 0;
}