c语言——分治法

解题思路:

        最大字段和求解我们有三种方法，一、就是暴力枚举法，这种方法思维比较简单，大概用三个for循环就可以实现了，但这个时间复杂度比较高，达到了o(n^3)所以我们在数量比较大的时候不推荐这种，当然本题也不能用这种。二、就是分治法，这种方法的时间复杂度是O(nlogn)，相对于前面小了很多。三、动态规划，它的时间复杂度是o(n)，这就跟小了。这里我只介绍第二种分治法，因为我还没学到，我也不会！哈哈哈！废话不多说，直接上思路:

        分治法的思路就是把一个问题分成若干个子问题，然后进行求解，当然了我们还需用到递归。分治法求解最大字段和的思维就是，把一个问题分成两段，这是我们就有三种情况，1、就是最大和在左边。2、最大和在右边。3、最大和在中间（也就是横跨左右两边）。求解中间的情况就把左右两边最大字段和加起来就好了。自己在草稿纸多画几遍就清楚了。本人水平有限，不懂的可以去b站搜索——最大字段和分治法就行了。给你们推荐一个讲的比较好的老师的视频，地址如下：https://www.bilibili.com/video/BV1YA41187t2?spm_id_from=333.337.search-card.all.click。就是他是用c++讲的，注意一下这就行了。

注意事项:
        注意递归是的出口就行了。
参考代码:

#include<stdio.h>

int a[100000];

int sort();

int midsum();

int maxc();

int main()

{

    int i,n;

    scanf("%d",&n);

    for(i=1;i<=n;i++){

        scanf("%d",&a[i]);

    }

    printf("%d",sort(1,n));  //这里我们直接调用分治的函数

    return 0;

}

int sort(int r,int l)        //这里定义分治函数，参数方别表示改字段的左右两端的下表

{

    int k,m,p;

    k=0,m=0,p=0;

    if(r==l)return a[r];     //当r等于l也就是只有一个元素的时候，此时的数当然是最大的，我们返回该值就行了

    int mid=(r+l)/2;

    k=sort(r,mid);          //对左边进行分治

    m=sort(mid+1,l);        //对右边进行分治

    p=midsum(r,mid,l);      //对处于横跨两边的字段和进行求解

    return maxc(k,m,p);

}

int midsum(int r,int mid,int l)   //定义一个参数分别表示左右两端和中间坐标的函数

{

    int left=a[r],right=a[l];    //这样定义的好处就是防止当数组全是负数情况下不会出错

    int i,sum=0,max;

    for(i=mid;i>=r;i--){           //对右边进行求和

        sum+=a[i];

        if(sum>left)left=sum;

    }

    for(i=mid+1;i<=l;i++){

        sum+=a[i];

        if(sum>left)right=sum;

    }

    int midsum=left+right;          //中间字段的最大值

    max=maxc(left,midsum,right);

    return max;                 //返回他们三个的最大值就行了

}

int maxc(int a,int b,int c)

{

    return (a>b?(a>c?a:c):(b>c?b:c));   //比较最大值

}