[C++知识库]最大字段和问题——分治法（C语言）

#include<stdio.h>
int MaxSubSum(int* arr, int letf, int right);
//时间复杂度O（nlogn）
int main() {
	int arr[] = { -2,11,-4,13,-5,-2 };
	int Max = MaxSubSum(arr, 0, sizeof(arr) / sizeof(int) - 1);
	printf("%d", Max);
	return 0;
}

int MaxSubSum(int* arr, int letf, int right) {
	int sum = 0;
	if (letf == right) {
		if (arr[letf] > 0) {
			sum = arr[letf];
		}
	}
	else {
		//递归
		int center = (letf + right) / 2;
		int letfsum = MaxSubSum(arr, letf, center);
		int rightsum = MaxSubSum(arr, center + 1, right);
		//计算从center往letf的最大值
		int s1 = 0;
		int letfs = 0;
		for (int i = center; i >= letf; i--) {
			letfs = letfs + arr[i];
			if (letfs > s1) {
				s1 = letfs;
			}
		}
		//计算从center往right的最大值
		int s2 = 0;
		int rights = 0;
		for (int i = center + 1; i <= right; i++) {
			rights = rights + arr[i];
			if (rights > s2) {
				s2 = rights;
			}
		}
		//求出最大子段和是否横跨左右两边
		sum = s1 + s2;
		if (sum < letfsum) {
			sum = letfsum;
		}
		if (sum < rightsum) {
			sum = rightsum;
		}
	}
	return sum;
}

创作打卡挑战赛

赢取流量/现金/CSDN周边激励大奖