编辑代码

#include <iostream>
using namespace std;
// 蛮力法
void manlifa(int a[],int n){
    int maxsum = 0;
    int cnt = 0;
    int sum =0;
    int count = 0;
    for(int k=0;k<n;k++){
        if(a[k]<0){
            cnt++;
        }
    }
    if(cnt==n){
        cout<<"蛮力法：最大子段和为："<<maxsum<<endl;
        return ;
    }
    for(int i=0;i<n;i++){
        sum = 0;
        for(int j=i+1;j<n;j++){
            count ++;
            sum += a[j];
        }
        if(sum>maxsum){
            maxsum=sum;
        }
    }
    cout<<endl;
    cout<<endl;
    cout<<"蛮力法：最大子段和为："<<maxsum<<endl;
    cout<<"蛮力法：处理次数："<<count<<endl;
    return ;
}

// 分治法
int maxsum(int a[],int left, int right,int &count){
  
    int sum=0,midsum=0,leftsum=0,rightsum=0;
    int center,s1,s2,lefts,rights;
    count++;
    if(left==right){
        sum=a[left];
    }
    else{
        center = (left+right)/2;
        leftsum = maxsum(a,left,center,count);
        rightsum = maxsum(a,center+1,right,count);
        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;
    
}
// 动态规划法
void maxsum1(int a[],int n){
    int b[n];
    int sum=0;
    int cnt = 0;
    b[0]=a[0];
    for(int i=1;i<n;i++){
        if(b[i-1]>0){
            cnt++;
            b[i]=b[i-1]+a[i];
        }
        else{
            cnt++;
            b[i]=a[i];
        }
    }
    for(int j=0;j<n;j++){
        if(b[j]>sum){
            sum=b[j];
        }
    }
    cout<<endl;
    cout<<endl;
   cout<<"动态规划法：最大子段和为："<<sum<<endl;
   cout<<"动态规划法：处理次数："<<cnt<<endl;
}
int main() {
    int a[6]={-5,3,-4,9,-1,6};
    //蛮力法
    manlifa(a,6);
   
    //分治法
    int count=0;
    int sum=0;
    sum = maxsum(a,0,5,count);
    cout<<endl;
    cout<<endl;
    cout<<"分治法：最大子段和为："<<sum<<endl;
    cout<<"分治法：处理次数："<<count<<endl;
   
    //动态规划法
    maxsum1(a,6);
	return 0;
}