题目链接 ：https://www.luogu.com.cn/problem/P1115

如题，先分析复杂度。  n的范围是 2* 10^5，对应之前总结的复杂度问题，nlogn可以解决  10^5，这个题能解决一半

从而这个题只能考虑n线性计算的复杂度，这里贪心算法 和 一维dp可以解决，两个方法思想上是一致的

先来分治，这个代码过不了会TLE，仅学习（这个代码是寒假集训时针对分治算法讲的）

#include<bits/stdc++.h>
using namespace std;
int a[200005];
int cnt;  //递归次数
int maxhe;  //最大和
int n;
int pos(int mid)
{
	int i;
	int maxl=0,ansl=a[mid];
	for(i=mid;i>=1;i--)
	{
		maxl+=a[i];
		ansl=max(maxl,ansl);
	}
	int maxy=0,ansy=a[mid+1];	
	for(i=mid+1;i<=n;i++)
	{
		maxy+=a[i];
		ansy=max(maxy,ansy);
	}
	return ansl+ansy;
}
int fen(int left,int right)
{
	int l,r;
	int mid;
	mid = (left+right)/2;
	if(left==right)
		return a[mid];
	else {
		int maxl=fen(left,mid);
		int maxy=fen(mid+1,right);
		int maxz=pos(mid); //横跨两边 
		return max(max(maxl,maxy),maxz);
	} 
}
int main()
{
	int i;
	cin>>n;
	for(i=1;i<=n;i++)
		cin>>a[i];
	cout<<fen(1,n)<<endl;
 } 

然后是贪心，这个比较好理解，就是我们用一个变量一直累加，一边累加一边判断去最大值，如果累加数变为了负数，那么我们就清零，之前的数不要了，重新从下一个数开始取

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll maxt = 2*1e5+5;
ll a[maxt];
ll s[maxt];
ll n;
int main()
{
	cin>>n;
	ll sum=0;ll ma=-99999999999;
	
	cin>>sum;
	ma=sum;
	
	for(ll i=2;i<=n;i++)
	{
		cin>>a[i];
		
		sum+=a[i]; 
		ma = max(ma,sum);
		
		if(sum<0)//贪心在后面，确保0不会被当做有效值 
			sum=0;
		
	}
	cout<<ma;
} 

最后是dp，这是一个线性的一维dp。

如果之前去过连续的几个数字大于0，那么我当前dp数组就在这个基础上加上我本身的数，否则就从我本身这个数重新计算

但是我本身这个数也不一定是个大数，，其实就是从贪心的角度上演变过来的

#include<bits/stdc++.h>
using namespace std;
int n,a[200020],b[200020],i,ans=-2147483647;
int main(){
   cin>>n;
   for(i=1;i<=n;i++){
       cin>>a[i];
       if(i<2) b[i]=a[i];
       else b[i]=max(a[i],b[i-1]+a[i]);
       ans=max(ans,b[i]);
   }
   cout<<ans;
   return 0;
}