时间限制: 1000 ms 内存限制: 65536 KB
【题目描述】
对于给定的整数序列A={a1,a2,...,an}，找出两个不重合连续子段，使得两子段中所有数字的和最大。我们如下定义函数 d(A)：
我们的目标就是求出d(A)。
【输入】
第一行是一个整数T(≤30)，代表一共有多少组数据。
接下来是T组数据。
每组数据的第一行是一个整数，代表数据个数据n(2≤n≤50000) ,第二行是n个整数a1,a2,...,an(|ai|≤10000)。
【输出】
输出一个整数，就是d(A)的值。
【输入样例】
1
10
1 -1 2 2 3 -3 4 -4 5 -5
【输出样例】
13
【提示】
就是求最大子段和问题，样列取2,2,3,−3,4和5，Baidu搜POJ 2479 Maximum sum，可获得大量经典最大子段和问题的题目解析，本题O(n^2)算法超时，必须用O(n)算法。
1. #include <iostream> 2. #include <cstdio> 3. #include <cstring> 4. #include <algorithm> 5. using namespace std; 6. const int N=50005; 7. int num[N]; 8. int Lsum[N]; 9. int Rsum[N]; 10. int main() 11. { 12. int t,n; 13. cin>>t; 14. while(t--){ 15. cin>>n; 16. for(int i=1;i<=n;i++) cin>>num[i]; 17. memset(Lsum,0,sizeof(Lsum)); 18. memset(Rsum,0,sizeof(Rsum)); 19. Lsum[1]=num[1]; 20. for(int i=1;i<=n;i++) 21. if(Lsum[i-1]>0) Lsum[i]=Lsum[i-1]+num[i]; 22. else Lsum[i]=num[i]; 23. Rsum[n]=num[n]; 24. for(int i=n-1;i>=1;i--) 25. if(Rsum[i+1]>0) Rsum[i]=Rsum[i+1]+num[i]; 26. else Rsum[i]=num[i]; 27. int maxn=-1000000; 28. int temp=-1000000; 29. for(int i=1;i<n;i++){ 30. temp=max(temp,Lsum[i]); 31. maxn=max(maxn,temp+Rsum[i+1]); 32. } 33. cout<<maxn<<endl; 34. } 35. return 0; 36. }
