Maximum-subarray problem

/*
Maximum-subarray problem
Given an array, find the subarray whose sum is the largest among all of the subarrays. The program prints the left index, right index and the sum of the subarray. The maximum-subarray problem is interesting only when the array containssome negative numbers.
The program uses divide-and-conquer algorithm described on Page68, Introduction to Algorithms.
Of course, this problem can be solved by using loops directly as the second program does.
*/


Solution one: divide-and-conquer

#include
using namespace std;

class subarray
{
public:
    int low;
    int high;
    int sum;
    subarray(int l, int h, int s)
    { low =l; high = h; sum = s;}
        
    // It's better to have a copy construtor
    // and operator= here. But since there are 
    // no reference and pointer members in
    // this class, the comopliers' synthetic
    // copy control works.
    // ~subarray() { cout << "subarray deleted" << endl; }
};

subarray  FindMaxCrossingSubarray(int a[], int low, int mid, int high);
subarray  FindMaxSubarray(int a[], int low, int high);

int main()
{
    int a[16] = {13, -3, -25, 20, -3, -16, -23, 
                 18, 20, -7, 12, -5, -22, 15, -4, 7} ;
    
    subarray result = FindMaxSubarray(a, 0, 15);
    cout << result.low << " " << result.high << " " << result.sum << endl;
    return 0;
}

// Divide-and-conquer
subarray  FindMaxSubarray(int a[], int low, int high)
{
    subarray result(low,high, a[low]);
    if ( low == high) return result;

    else 
    {
        int mid = (low + high)/2;
        // Find max-subarray, right-subarray and crossing-subarray 
        subarray leftSubarray = FindMaxSubarray(a, low, mid);
        subarray rightSubarray = FindMaxSubarray(a, mid+1, high);
        subarray crossingSubarray = FindMaxCrossingSubarray(a, low, mid, high);
       
        if (leftSubarray.sum >= rightSubarray.sum &&
            leftSubarray.sum >= crossingSubarray.sum)
            return leftSubarray;
        else if (rightSubarray.sum >= leftSubarray.sum &&
                 rightSubarray.sum >= crossingSubarray.sum)
            return rightSubarray;
        else 
            return crossingSubarray;
    }
}

subarray FindMaxCrossingSubarray(int a[], int low, int mid, int high)
{
    int leftSubarraySum = -99999999;
    int sum = 0;
    int maxLeft;
    int maxRight;

    for (int i = mid; i >= low; i--)
    {
        sum += a[i];
        if (sum > leftSubarraySum)
        {   
            leftSubarraySum = sum;
            maxLeft = i;
        }
    }

    int rightSubarraySum = -99999999;
    sum = 0;
    for ( int j = mid + 1; j <= high; j++)
    {
        sum += a[j];
        if (sum > rightSubarraySum)
        {
            rightSubarraySum  = sum;
            maxRight = j;
        }
    }

    subarray result(maxLeft, maxRight, 
                                    leftSubarraySum + rightSubarraySum);
    return result;     
}

Solution 2: Trivial method

#include
using namespace std;

int maxSum =  -9999;
int leftIndex, rightIndex;

int main()
{
    int a[16] = {13, -3, -25, 20, -3, -16, -23,
                18, 20, -7, 12, -5, -22, 15, -4, 7} ;

    /*  int b[20] = {13, -3, -25, 20, -3, -16, -23,
                 18, -2, 5,  20, -7, 12, -5,4 -22,7, 15, -4, 7} ;
    */
//    f(a, 0, 16);
    // f(b, 0, 20);
    int sum = 0;
    for(int start = 0; start < 16; start++)
    {
        sum = 0;
        for (int i = start; i < 16; i++)
        {
            sum += a[i];
            if (sum > maxSum)
            {
                maxSum = sum;
                leftIndex = start;
                rightIndex = i;
            }
        }
    }
// f(a,start+1, size);

  cout << "The maximum-subarray is from a[" << leftIndex
         << "] to a[" << rightIndex << "]" << endl;
    cout << "Its sum is :  " << maxSum << endl;

    return 0;
}