分治策略-最大子数组问题

给出数组

A[16] = {13，-3，-25，20，-3，-16，-23，18，20，-7，12，-5，-22，15，-4，7}

求其最大子数组，最后返回边界与和值。

算法如下（具体值可在主函数中给出）：

#include<iostream>
#include<algorithm>
#define INFO -999999
#include<math.h>
using namespace std;

typedef struct array1 {
	int low;
	int mid;
	int high;
};

struct array1 find_max_crossing(struct array1 *a,int A[]) {
	static struct array1 sum1;
	int left_sum = INFO;
	int sum = 0, i;
	int max_left;
	for (i = a->mid; i >= a->low; --i) {
		sum += A[i];
		if (sum > left_sum) {
			left_sum = sum;
			max_left = i;
		}
	}
	sum1.low = max_left;
	int right_sum = INFO;
	sum = 0;
	int j;
	int max_right;
	for (j = a->mid + 1; j <= a->high; ++j) {
		sum += A[j];
		if (sum > right_sum) {
			right_sum = sum;
			max_right = j;
		}
	}
	sum1.high = max_right;
	sum1.mid = max_left + max_right;
	return sum1;
}

struct array1 find_maximum_subarray(int A[], int low, int high) {
	static struct array1 result[4];
	struct array1 *a;
	a->low = low;
	a->high = high;
	a->mid = floor((low + high) / 2);
	if (high == low) {
		result[0].low = low;
		result[0].high = high;
		result[0].mid = A[low];
		return result[0];
	}
	else {
		int mid1 = floor((low + high) / 2);
		result[1] = find_maximum_subarray(A, low, mid1);
		result[2] = find_maximum_subarray(A, mid1 + 1, high);
		result[3] = find_max_crossing(a, A);
		if (result[1].mid >= result[2].mid&&result[1].mid >= result[3].mid)
			return result[1];
		else if (result[2].mid >= result[1].mid&&result[2].mid >= result[3].mid)
			return result[2];
		else
			return result[3];
	}

}