最大字段和问题（动态规划、暴力枚举、分治递归）_动态算法实现最大字段和问题c++实现

在网上搜索了很多的分治递归的算法，发现很多运行不了，这里有一个最重的坑就是在分治算法函数形参中不能用0~n，而必须是0~(n-1)，具体什么原因还没想明白，我也尝试改变函数中在求中值mid时考虑到数组长度为奇数还是偶数的情况，但是最终还是不行，不如最开始就直接改成n-1，后面的代码也都好写了，暂时还没想明白，有大佬懂的希望在评论解释一下，谢！

代码如下：注释都比较详细了，都能运行

#include<bits/stdc++.h>
using namespace std;
 
//动态规划算法
int Dynamic(int arr[],int n){
    int max = arr[0];//定义max，存储最大和，赋初始值数组第一个元素
    int sum = 0;//作为过度加法，计算整个数组每一段的和
    for(int i =0;i<n;i++){
        sum += arr[i];//首先更新sum的值
        if(sum < arr[i]){//如果sum加上arr[i]后发现比它本身值还小，那么就要更新sum值
            sum = arr[i];//更新sum到当前元素位置开始加和
        }
        if(sum > max){//每次更新后的sum值与max相比较，如果此时sum更大则更新max值
            max = sum;
        }
    }
    return max;//返回最大子段和
}
//暴力穷举法
int FindMax(int arr[],int n){
    int max = arr[0];
    int sum = 0;
    for(int i = 0;i<n;i++){//遍历所有情况
        sum = 0;
        for(int j = i;j<n;j++){
            sum += arr[j];
            if(sum > max){
                max = sum;
            }
        }
    }
    return max;
}
//分治思想求解,right必须是数组的最后元素的下标(n-1)！！！
int Divide(int arr[],int left,int right){
    //如果左右标相等，表明递归到最深层，递归结束
    if(left == right)
        return arr[left];
    
    //处理最大字段在mid左右两边的情况
    int mid = (left+right)/2;
    int leftSum = Divide(arr,left,mid);
    int rightSum = Divide(arr,mid+1,right);
    
    //处理最大字段在中间的情况
    int lSum = 0;//一直加。。。
    int rSum = 0;//一直加。。。。
    int lmax = 0;//记录加的过程中左边的最大和
    int rmax = 0;//记录加的过程中右边最大和
    
    //先从中间往左边加，只记录最大值lSum
    for(int l = mid;l>=left;l--){
        lSum += arr[l];
        lmax = lSum>lmax?lSum:lmax;
    }//再从中间往右边加，记录最大值rSum
    for(int r = mid+1;r<=right;r++){
        rSum += arr[r];
        rmax = rSum>rmax?rSum:rmax;
    }
    int midSum = lmax+rmax;//记录中间字段和
    
    //返回三种情况的最大值
    return max(max(leftSum,rightSum),midSum);
}
int main() {
    int n;
    cin >> n;
    int arr[n];
    for(int i = 0;i<n;i++){
        cin >> arr[i];
    }
    int a = Dynamic(arr,n);
    int b = FindMax(arr,n);
    int c = Divide(arr,0,n-1);//right必须是数组的最后元素的下标(n-1)
    cout << "使用动态规划法得到的结果为：" << a << "\n";
    cout << "使用穷举法得到的结果为：" << b << "\n";
    cout << "使用分治法得到的结果为：" << c ;
    return 0;
}