最大子段和问题： 给定由n个整数（可能有负整数）组成的序列（a1，a2，···，an），最大子段和要求该序列形如 ( ∑ k = i j a k ) \displaystyle ( \sum_{k=i}^j a_k ) (k=i∑jak)的最大值(1 ≤ \displaystyle\leq ≤i ≤ \displaystyle\leq ≤j ≤ \displaystyle\leq ≤n)。例如，序列（-20,11，-4,13，-5，-2）的最大子段和为 ( ∑ k = 2 4 a k ) \displaystyle ( \sum_{k=2}^4 a_k ) (k=2∑4ak)=20。
#include<iostream> using namespace std; int MaxSum(int a[],int left,int right) { int sum=0,midSum=0,leftSum=0,rightSum=0; int center,s1,s2,lefts,rights; if(left==right) sum=a[left]; else{ center=(left+right)/2; leftSum=MaxSum(a,left,center); rightSum=MaxSum(a,center+1,right); s1=0;lefts=0; for(int i=center;i>=left;i--) { lefts+=a[i]; if(lefts>s1) s1=lefts; } s2=0; rights=0; for(int j=center+1;j<=right;j++) { rights+=a[j]; if(rights>s2) s2=rights; } midSum=s1+s2; if(midSum<leftSum) sum=leftSum; else sum=midSum; if(sum<rightSum) sum=rightSum; } return sum; } int main() { int a[1000]; int n; cin>>n; for(int i=0;i<n;i++) cin>>a[i]; cout<<MaxSum(a,0,n-1); }