此题解法多样
首先，假定有区间[l..r]，其中间位置为mid，其最大子段为[i..j。那么显然，ii和jj必定符合下列三种情况之一：
只需要分别求出三种情况下的值，取其最大的即可。
其中，很容易求出第二种情况，即求出区间[i..mid]与区间[mid+1..j]，将其相加即可。复杂度O(n)
如何处理第一种和第三种情况呢？也不难发现，第一种情况，其实就是求区间[1..mid]中的最大值，第三种情况就是求区间[mid+1..r]中的最大值。那么，只需递归求出即可。
显然，该解法的复杂度为 O(nlogn) 通过此题是没问题的。
附上代码
#include<cstdio> int n , arr[200200]; //arr存储该序列 const int minn = -19260817; // 定义最小值 inline int Max( int a , int b) { return a > b ? a : b ;} //自定义 Max 函数（好像比stl的快一点） int rec( int l , int r ) { //分治函数 if ( l == r ) { // l=r时，直接返回该位置的值 return arr[l]; } int mid = ( l + r ) >> 1; int sum = 0 , ret1 = minn , ret2 = minn; //ret1为[l..mid]区间内包含mid的最大子段和，ret2为[mid+1..r]区间内包含(mid+1)的最大子段和 for( int i = mid ; i >= l ; i-- ) { sum += arr[i]; ret1 = Max( ret1 , sum ); } //求出[i..mid]区间最大值 sum = 0; for( int i = mid+1 ; i <= r ; i++ ) { sum += arr[i]; ret2 = Max( ret2 , sum ); } //求出[mid+1..r]区间最大值 return Max( Max( rec( l , mid ) , rec( mid + 1 , r ) ) , ret1 + ret2 ); //返回可能一 可能二 可能三 中的最大值 } int main() { // 以下主函数 scanf("%d", &n ); for( int i = 1 ; i <= n ; i++ ) { scanf("%d" , &arr[i] ); } printf("%d" , rec(1 , n) ); return 0; }
2.DP
这道题其实是练习DP的入门题（本蒟蒻也才刚刚学DP）
首先，通过题意，我们可以了解到：
f[i]=max(f[i-1]+n[i],n[i])
但是！
f[n]的值并不一定是最终结果
比如这个输入：
5 233 233 -666 1 1
如果直接输出f[n]的值，结果会是2，但是答案应该为466！
为什么？
因为若f[i]的值为负数，则f[i+1]的值就是n[i],而n[i]的值不一定比前面的最大字段和数大！
（或者n[i]为负数，则f[i]小于f[i-1]!)
所以，我们还要再用一个数从1到n再查找一次，才能找出最大数！！！
代码（时间复杂度大概是O(n）？算了，反正我也不晓得）：
#include<bits/stdc++.h> using namespace std; int main() { int n[200001],p,ans[200001]={0}; int sum=-9999999;//|x|<=10000 QWQ cin>>p; for(int i=1;i<=p;i++) { cin>>n[i];//输入 ans[i]=max(ans[i-1]+n[i],n[i]);//DP sum=max(sum,ans[i]);//取最大值也同时进行，节约时间 } cout<<sum;//直接输出 return 0; }
我的想法也是贪心，就是用一个sum记录当前前缀和，一路累积过去，如果前缀和sum变成了负数，那么下一个数就不需要前面的数了（因为还不如只选它一个），这时把sum置为0，再继续累加。
我写了一个挺短的代码，（从A+B题解那里学到了好多东西）：
#include<cstdio> int n,j,sum,maxx;int main(){ scanf("%d%d",&n,&maxx);sum=maxx;//输入n while(--n){scanf("%d",&j);sum=sum>0?sum:0;sum+=j;maxx=maxx>sum?maxx:sum;}//贪心，如果负了就舍去 return (printf("%d",maxx))&0;//输出并return 0 }
因为前几天hack掉了几个思想很好但是没有注意细节的题解，所以来这填坑（包括之前题解的思想，用自己语言解释）
DP什么的下面的dalao们都讲得够明白了，这里仅介绍空间上的优化
因为是DP，所以不用储存从第一个到最后一个的答案，可以使用滚动数组，仅两个元素，轮流储存。每次通过前一个算出后一个，然后将前一个删除
代码如下：
#include<cstdio> #include<cmath> #include<iostream> using namespace std; int sum,a[2],n;//仅需要两个元素的数组 int main() { scanf("%d",&n); scanf("%d",&a[1]);//先读入第一个元素 sum=a[1]; for(int i=2;i<=n;++i) { if(sum<0) sum=0;//因为第一个输入的数可能是负数，所以这个判断放for循环的最前面 scanf("%d",&a[i%2]);//滚动 sum+=a[i%2]; a[i%2]=max(a[(i-1)%2],sum);//DP状态转移方程 } printf("%d",a[n%2]); return 0; }
原文：https://www.cnblogs.com/pxy071128fzm/p/14105407.html