最大子段和

#include<iostream>
using namespace std;

//如( -2,11,-4,13,-5,-2 )最大子段是{ 11,-4,13 }其和为20
//分治：将arr[1:n]分成arr[1:n/2]和arr[n/2+1:n]，那么最大值可能有以下三种情况
//1：maxSum在arr[1:n/2]中
//2：maxSum在arr[n/2+1:n]中
//3：maxSum在arr[i:j]中，并且1<=i<=n/2,n/2+1<=j<=n;
//时间复杂度：递归方程，T(n)=2T(n/2)+O(n)，结果为O(nlogn)
int MaxSumHelp(int left,int right,int arr[]){
    if(left==right){        //边界条件，不要忘记！
        return arr[left]>0?arr[left]:0;
    }

    int center=(left+right)/2;

    //获得1、2情况的最大值
    int leftMaxSum=MaxSumHelp(left,center,arr);
    int rightMaxSum=MaxSumHelp(center+1,right,arr);

    //获得3情况的最大值，需要从center（向左），center+1（向右），分别向两边计算，即固定了起点
    int lefts=0,s1=arr[center];     //此时一定：s1<=最大值
    for(int i=center;i>=left;i--){
        lefts+=arr[i];
        if(s1<lefts){
            s1=lefts;　　//s1用于记录以arr[center]为边的最大值
        }
    }

    int rights=0,s2=arr[center+1];
    for(int i=center+1;i<=right;i++){
        rights+=arr[i];
        if(s2<rights){
            s2=rights;    //s2用于记录以arr[center+1]为边的最大值
        }
    }

    int sum=s1+s2;

    //比较3种情况的sum，获得本次的最大和
    if(sum<leftMaxSum){
        sum=leftMaxSum;
    }
    if(sum<rightMaxSum){
        sum=rightMaxSum;
    }

    return sum;
}

int MaxSum(int n,int arr[]){
    return MaxSumHelp(0,n-1,arr);
}

int main(){
    int arr[6]={-2,11,-4,13,-5,-2};
    int n=6;

    cout<<MaxSum(n,arr)<<endl;
    system("pause");
    return 0;
}

 1 #include<iostream>
 2 using namespace std;
 3 
 4 //如( -2,11,-4,13,-5,-2 )最大子段是{ 11,-4,13 }其和为20
 5 //动态规划：
 6 //假设b[j]表示arr[i:j]的最大和，即以a[j]为终点的最大值，不管a[j]是否是负数，必须包含它
 7 //那么如果b[j-1]>0,b[j]=b[j-1]+arr[j]，否则b[j]=arr[j],
 8 //其中由max来记录曾经有过的最大和，那么一次循环结束后，就能得到最大子段和
 9 //动态规划递推式：
10 
11 int MaxSum(int n,int arr[]){
12     int b=0,max=arr[0];         //此刻一定有:max<=最终最大和，不要之间设置成0，因为所给数组可能全部<0
13     for(int i=0;i<n;i++){
14         if(b>0)
15             b+=arr[i];
16         else
17             b=arr[i];
18         
19         if(max<b)
20             max=b;
21     }
22     return max;
23 }
24 
25 int main(){
26     int arr[6]={-2,11,-4,13,-5,-2};
27     int n=6;
28 
29     cout<<MaxSum(n,arr)<<endl;
30     
31     system("pause");
32     return 0;
33 }