最大子段和

问题描述

求一个序列的最大子段和即最大连续子序列之和。例如序列[4, -3, 5, -2, -1, 2, 6, -2]的最大子段和为11=[4+(-3)+5+(-2)+(-1)+(2)+(6)]。

方法一：分治

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 
 7 int MaxSubSum(const int arr[],int l,int r){
 8     int sum=0;
 9     if(l==r) 
10         return arr[l];
11     else{
12         int mid=l+(r-l)/2;
13         int lsum=MaxSubSum(arr,l,mid);
14         int rsum=MaxSubSum(arr,mid+1,r);
15         int s1=0;
16         int lefts=0;
17         for(int i=mid; i>=l; i--){
18             lefts+=arr[i];
19 //            s1=max(lefts,s1);
20             if(lefts>s1) s1=lefts;
21         }
22         int s2=0;
23         int rights=0;
24         for( int i=mid+1; i<=r; i++ ){
25             rights+=arr[i];
26 //            s2=max(rights,s2);
27             if(rights>s2) s2=rights;
28         }
29         sum=s1+s2;
30         sum=max(sum,max(lsum,rsum));
31         return sum;
32     }
33 }
34 
35 int main(){
36     const int a[] = { 4, -3, 5, -2, -1, 2, 6, -2 };
37     int maxSubSum=MaxSubSum(a,0,7);
38     cout<<maxSubSum<<endl;
39 
40 
41     return  0;
42 }

方法二：动态规划

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn = 20;
 7 
 8 int main(){
 9     const int a[] = { 0,4, -3, 5, -2, -1, 2, 6, -2 };
10     int b[maxn];
11     memset(b,0,sizeof(b));
12     int sum=0;
13     int len =sizeof(a)/sizeof(int);
14     for( int i=1; i<len; i++ ){
15         if(b[i-1]>0) b[i]=b[i-1]+a[i];
16         else b[i]=a[i];
17         sum=max(sum,b[i]);
18     }
19     cout<<sum<<endl;
20 
21     return 0;
22 }

。。。。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 20;
int sum[maxn];

int main(){
    memset(sum,0,sizeof(sum));
    const int a[] = { 0,4, -3, 5, -2, -1, 2, 6, -2 };
    int len =sizeof(a)/sizeof(int);
    for( int i=1; i<=len; i++ ){
        sum[i]=sum[i-1]+a[i];
    }
    for( int i=0; i<len; i++ ){
        cout<<sum[i]<<" ";
    }
    cout<<endl;
    int ove_min=INF;
    int ove_max=-INF;
    for( int i=0; i<len; i++ ){
        ove_min=min(ove_min,sum[i]);
        ove_max=max(ove_max,sum[i]);
    }
    cout<<ove_max<<" "<<ove_min<<endl;

    return 0;
}

有些目标看似很遥远，但只要付出足够多的努力，这一切总有可能实现！