蓝桥杯算法提高VIP-和最大子序列 （C语言代码）分治法

解题思路:

注意事项:

参考代码:

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 100001;
int a[maxn];
int maxsum(int *A, int x, int y)   //返回左闭右开区间[x,y)中的最大连续和
{
	int v, L, R, maxs;
	if(y-x == 1) return A[x];
	int m = x + (y-x)/2;       //划分
	maxs = max(maxsum(A,x,m),maxsum(A,m,y));
	v = 0;
	L = A[m-1];
	for(int i = m-1; i >= x; --i)    //合并
	{
		L = max(L, v += A[i]);
	}
	v = 0;
	R = A[m];    
	for(int i = m; i < y; ++i)       //合并
	{
		R = max(R, v += A[i]);
	}
	return max(maxs,L+R);
}
int main()
{
	int T;
	scanf("%d", &T);
	for(int i = 0; i < T; ++i)
	{
		scanf("%d", &a[i]);
	}
	printf("%d\n", maxsum(a,0,T));
	return 0;
}