最大子数组

#include <iostream>
#include <vector>
using namespace std;

void print_vector(vector<int> nums) {
	for (int i = 0; i < nums.size(); i++) {
		cout << nums[i] << ' ';
	}
}

vector<int> Find_Max_Cross_SubArray(vector<int> nums, int low, int mid, int high) {
	int sum = 0;
	int left_sum = -100000;
	int left = mid;
	int right_sum = -100000;
	int right = mid + 1;
	for (int i = mid;i>=low; i--) {
		sum += nums[i];
		if (sum >= left_sum) {
			left_sum = sum;
			left = i;
		}
	}
	sum = 0;
	for (int i = mid + 1; i <= high; i++) {
		sum += nums[i];
		if (sum > right_sum) {
			right_sum = sum;
			right = i;
		}
	}
	return { left,right,left_sum + right_sum };
}

vector<int> Find_Max_SubArray(vector<int> nums, int low, int high) {
	if (low >= high) 
		return {low,high,nums[low] };
	int mid = (low + high) / 2;
	vector<int> left_result = Find_Max_SubArray(nums, low, mid);
	vector<int> right_result = Find_Max_SubArray(nums, mid + 1, high);
	vector<int> mid_result = Find_Max_Cross_SubArray(nums, low, mid, high);
	if (mid_result[2] > left_result[2] && mid_result[2] > right_result[2])
		return mid_result;
	else if (left_result[2] > right_result[2])
		return left_result;
	else
		return right_result;
}

void main() {
	vector<int> nums5 = { 2, -1, -2, 1, -3, 4, -2, 2, -1, 5 };
	// 结果: 7 (子数组 [4, -2, 2, -1, 5])
	vector<int> result = Find_Max_SubArray(nums5, 0, nums5.size() - 1);
	cout << result[0] << ' ' << result[1];
}