分治法求解最大子段和

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;
}