C C++ 最大子列和

8
4 -3 5 -2 -1 2 6 -2
11

#pragma warning(disable : 4996)
#include
using namespace std;

const int MaxSize = 100001;

int myFind(int a[], int low, int high);
int myFindCross(int a[], int low, int mid, int high);
int myFindMax(int x, int y, int z);

int main() {
	int a[MaxSize] = { 0, };
	int num;
	cin >> num;
	for (int i = 0; i < num; i++)
		cin >> a[i];
	int res = myFind(a, 0, num - 1);
	cout << res;
	return 0;
}

int myFind(int a[], int low, int high) {
	if (low == high)
		return a[low];
	else {
		int mid = (low + high) / 2;
		int left_sum = myFind(a, low, mid);
		int right_sum = myFind(a, mid + 1, high);
		int cross_sum = myFindCross(a, low, mid, high);
		return myFindMax(left_sum, right_sum, cross_sum);
	}
}

int myFindCross(int a[], int low, int mid, int high) {			//线性复杂度
	int left_c = 0;				//所以至少为0
	int right_c = 0;
	int sum = 0;
	for (int i = mid; i >= low; i--) {
		sum += a[i];
		if (sum > left_c)
			left_c = sum;
	}
	sum = 0;				//记得重置
	for (int i = mid + 1; i <= high; i++) {
		sum += a[i];
		if (sum > right_c)
			right_c = sum;
	}
	return left_c + right_c;
}

int myFindMax(int x, int y, int z) {
	int max = 0;
	if (x > max)
		max = x;
	if (y > max)
		max = y;
	if (z > max)
		max = z;
	return max;
}