Finding maximal subarray (divide and conquer)

[pinkk]

Hello everyone. I would like a hint or just some pointing out at what I'm doing wrong. The findMaximalSubarray function doesn't have a return type; the result is stored in a struct called msaAnswer and the struct has the member variables high (for the end index of the maximal subarray), low (for the beginning index of the maximal subarray), and sum (for the total sum of the entries in that subarray).

Here's my implementation of the function:

#include "maxsubarray.h"
#include <iostream>
using std::endl;

namespace myName
{
    void findMaxSubarray(long* A, long low, long high, msaAnswer& result)
    {
        if (high == low)
        {
            result.low = low;
            result.high = high;
            result.sum = A[low];
        }
        else
        {
            msaAnswer left_result;
            msaAnswer right_result;
            msaAnswer cross_result;
            unsigned long mid = (low + high)/2;
            unsigned long left_tmp = 0;
            unsigned long right_tmp = 0;
            unsigned long sum = 0;
            unsigned long max_left = mid;
            unsigned long max_right = mid;
            
            for (int i = mid - 1; i > low - 1; i--)
            {
                sum = sum + A[i];
                if (sum > left_tmp)
                {
                    left_tmp = sum;
                    max_left = i;
                }
            }
            sum = 0;
            for (int j = mid + 1; j < high + 1; j++)
            {
                sum = sum + A[j];
                if (sum > right_tmp)
                {
                    right_tmp = sum;
                    max_right = j;
                }
            }
            cross_result.low = max_left; 
            cross_result.high = max_right;
            cross_result.sum = left_tmp + right_tmp;
            
            findMaxSubarray(A, low, mid, left_result);
            findMaxSubarray(A, mid, high, right_result);
            
            
            
            if ((left_result.sum >= right_result.sum) && (left_result.sum >= cross_result.sum))
            {
                result.low = left_result.low;
                result.high = left_result.high;
                result.sum = left_result.sum;
            }
            else if ((right_result.sum >= left_result.sum) && (right_result.sum >= cross_result.sum))
            {
                result.low = right_result.low;
                result.high = right_result.high;
                result.sum = right_result.sum;
            }
            else
            {
                result.low = cross_result.low;
                result.high = cross_result.high;
                result.sum = cross_result.sum;
            }
        }
    }
}

And here's the main program (modified) to test it:

#include <fstream>
using std::ofstream;
using std::endl;
#include <iostream>
using std::cout;
#include <stdlib.h> //for rand()

#include "maxsubarray.h"
using namespace myName;

void randomFill(long* A, unsigned long size);
void printArray(long* A, unsigned long size);

//const bool smalltest = true;
const bool smalltest = false;

int main(void)
{
	srand(1); //after you think things are working, you can change this to run different tests.
	unsigned long n;
	n = 10;
	long* A = new long[n];
    msaAnswer rslt;
    //,rslttest,rsltlinear;
	unsigned long i;
	for(i=0; i<3; i++)
	{
		::randomFill(A,n);
		myName::findMaxSubarray(A,0,n-1,rslt);
		//myName::findMaxSubarray_linear(A,0,n-1,rsltlinear);
		//myName::findMaxSubarraySlow(A,0,n-1,rslttest);
		printArray(A,n);
		cout << rslt << endl;
        //rsltlinear << rslttest << endl <<
	}
	if(smalltest) return 0;
	//else, run bigger tests and write results to a file.

	std::ofstream fout;
	fout.open("output"); //should overwrite whatever file is currently there.

	delete[] A;
	n = 100;
	A = new long[n];

	for(i=0; i<10; i++)
	{
		::randomFill(A,n);
		myName::findMaxSubarray(A,0,n-1,rslt);
		//myName::findMaxSubarray_linear(A,0,n-1,rsltlinear);
		//myName::findMaxSubarraySlow(A,0,n-1,rslttest);
		fout << rslt << " @\n";
        //<< rsltlinear << rslttest 
	}
	fout.close();

	return 0;
}

void randomFill(long* A, unsigned long size)
{
	for(unsigned long i=0; i<size; i++)
		A[i] = (::rand()%myName::maxrand) - (myName::maxrand / 2);
}

void printArray(long* A, unsigned long size)
{
	for(unsigned long i=0; i<size; i++)
		cout << A[i] << " ";
	cout << endl;
}

As soon as I compile this and try to run the .exe file, the program crashes. I have a feeling it has to do with my use of msaAnswer left_result, right_result, etc. but I do not see a way to achieve what I want to do otherwise. Any hints or suggestions would be appreciated.