C算法分析与设计——蛮力法分治法求解最大子段和

实验内容：
（1） a[1:n]的最大子段和与a[1:n/2]的最大子段和相同
（2） a[1:n]的最大子段和与a[n/2+1:n]的最大子段和相同
（3） a[1:n]的最大子段和为a[i]+…+a[j]，并且1<=i<=n/2，n/2+1<=j<=n。
#include <stdio.h>
#include <stdlib.h>
/**
 * 产生一个数组
 * @param a 空数组
 * @return 数组长度count
 */
int produceSZ(int a[])
{
    int i;
    int count;

    printf("请输入数组个数：\n");
    scanf("%d", &count);

    for (i = 0; i < count; i++)
    {
        printf("请输入第%d个数\n", i + 1);
        scanf("%d", &a[i]);
    }

    for (i = 0; i < count; i++)
    {
        printf("%d\t", a[i]);
    }
    printf("\n");

    return count;
}


/**
 *分治法
 * @param left 起始位置
 * @param right 结束位置
 * @return index[0]最大子段和、index[1]起始位置、index[2]结束位置
 */
int *maxsub(int a[], int left, int right)
{
    int center;//中位数
    int sum;
    int left_max;
    int right_max;
    int i;
    int *index;
    int *left_Sub;//情况一的最大子段和
    int *right_Sub;//情况二的最大子段和
    int *index_left;
    int *index_right;

    index = (int *) malloc(sizeof(int) * 3);//申请空间
    left_Sub = (int *) malloc(sizeof(int) * 3);
    right_Sub = (int *) malloc(sizeof(int) * 3);
    index_left = (int *) malloc(sizeof(int) * 3);
    index_right = (int *) malloc(sizeof(int) * 3);

    center = (left + right) / 2;
    if (left == right)
    {
        index[0] = a[left];
        index[1] = left;
        index[2] = right;
    }
    else
    {
        left_Sub = maxsub(a, left, center);//情况1，递归求解
        right_Sub = maxsub(a, center + 1, right);//情况二，递归求解
        /*
         * 计算情况三的最大子段和
         */
        sum = 0;
        left_max = 0;
        for (i = center; i >= left; i--)
        {
            sum += a[i];
            index_left[2] = center;
            if (sum > left_max)
            {
                left_max = sum;
                index_left[0] = sum;
                index_left[1] = i;
            }
        }
        sum = 0;
        right_max = 0;
        for (i = center + 1; i <= right; i++)
        {
            sum += a[i];
            index_right[1] = center + 1;
            if (sum > right_max)
            {
                right_max = sum;
                index_right[0] = sum;
                index_right[2] = i;
            }
        }
        /*
         *比较三种情况，找出子段和数值最大的情况
         */
        sum = right_max + left_max;
        index[0] = sum;//先假定第三种情况的子段和最大
        index[1] = index_left[1] + 1;//加一是为了返回逻辑位置
        index[2] = index_right[2] + 1;
        if (sum < left_Sub[0])  //相互比较
        {
            index[0] = left_Sub[0];
            index[1] = left_Sub[1] + 1;
            index[2] = left_Sub[2] + 1;
        }
        if (sum < right_Sub[0])
        {
            index[0] = right_Sub[0];
            index[1] = right_Sub[1] + 1;
            index[2] = right_Sub[2] + 1;
        }
    }
    return index;
}

/**
 * 蛮力法
 * @param a 数组
 * @param len 数组长度
 * @return index[0]最大子段和、index[1]起始位置、index[2]结束位置
 */
int *maxSum(int a[],int len)
{
    int maxSum = 0;
    int sum = 0;
    int *index;
    int i;
    int j;

    index = (int *) malloc(sizeof(int) * 3);//申请空间

    for(i = 0; i < len; i++) //从第一个数开始算起
    {
        sum = a[i];
        for(j = i + 1; j < len; j++)//从i的下一个数开始
        {
            a[i] += a[j];
            if(a[i] > sum)
            {
                sum = a[i];//每一趟的最大值
                if(a[i] > maxSum)
                {
                    index[2] = j + 1;//储存结束点的逻辑位置的坐标
                }
            }
        }

        if(sum > maxSum)
        {
            maxSum = sum;
            index[0] = sum;
            index[1] = i + 1;//储存起始点的逻辑位置的坐标

        }
    }
    return index;
}
int main(int argc, char *argv[])
{
    int a[100];//a的空间大小根据情况来定，给的稍微大些，这里给了100
    //  int b[100];
    int *max;
    // int *max1;
    int *max2;
    int len;//数组长度

    len = produceSZ(a);

    printf("********分治法********\n");
    /*
    之所以第三个参数为len-1
    是因为在  计算情况三的最大子段和的时候
    从center+1一直加到right(包含right)
    */
    max = maxsub(a, 0, len - 1);
    printf("max = %d\n", max[0]);
    printf("start = %d\n", max[1]);
    printf("end = %d\n", max[2]);

    printf("********蛮力法********\n");
    max2 = maxSum(a, len);
    printf("max = %d\n", max2[0]);
    printf("start = %d\n", max2[1]);
    printf("end = %d\n", max2[2]);
    return 0;
}