分治法求解最大子段和

1.算法基本思想

分治法求最大子段和：利用分治算法先划分为若干个子问题，递归求解每一个子问题，最后将子问题合并，从而求解到整个问题的解。

2.主要数据结构及其作用

一维数组：存储并记录数据

3.测试用例：

4.实验结果截图：

测试用例1

测试用例2

测试用例3

5.代码实现

#include<iostream>
using namespace std;
int besti,bestj;
int MaxSubSum(int *a,int left,int right)
{

    int sum=0;
    if(left==right){
        sum=a[left]>0?a[left]:0;
        besti=left;
        bestj=right;
    }

    else
    {
        int center=(left+right)/2;
        int leftsum=MaxSubSum(a,left,center);
        int rightsum=MaxSubSum(a,center+1,right);
        int s1=0;int lefts=0;
        for(int i=center; i>=left; i--)
        {
            lefts+=a[i];
            if(lefts>s1){
                s1=lefts;
                besti=i;
            }

        }
        int s2=0;int rights=0;
        for(int i=center+1; i<=right; i++)
        {
            rights+=a[i];
            if(rights>s2){
                s2=rights;
                bestj=i;
            }

        }
        sum=s1+s2;
        if(sum<leftsum)sum=leftsum;
        if(sum<rightsum)sum=rightsum;
    }
    return sum;
}
int main()
{
    int n;
    cout<<"请输入需要输入的元素的个数："<<endl;
    cin>>n;
    int a[n];
    cout<<"请输入"<<n<<"个元素："<<endl;
    for(int i=0; i<n; i++)
        cin>>a[i];
    cout<<"最大子段和为:"<<MaxSubSum(a, 0, n-1)<<"  ";
    cout<<"起始下标:"<<besti+1<<"终止下标:"<<bestj+1<<endl;
}