用分治法求最大连续子序列和的记录

前言

今天在看书中用分治法求最大连续子序列和的例子，自己想了很久。题目描述如下：
给定K个整数的序列{ N1, N2, ..., NK }，其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj }，其中 1 <= i <= j <= K。最大连续子序列是所有连续子序列中元素和最大的一个，例如给定序列{ -2, 11, -4, 13, -5, -2 }，其最大连续子序列为{ 11, -4, 13 }，最大和为20。输出最大连续子序列和
书中有4种方法可以来解，当时心中那个感叹啊，牛逼！其中第一种和第二种差不多，但自己对其分治方法感兴趣而已。在学习的过程中，自己想着怎么并把最大连续子序列打印出来。

第一种O(N^2)的解法

简单粗暴，以每个元素为起点来遍历。输出最大子序列。

int MaxSubSum (int a[], int n)
{
    int i, j, maxSum = 0;

    int left = 0;  //用来记录最大子序列的第一个元素
    int right = 0; //用来记录最大子序列的最后一个元素
    for (i = 0; i < n; i++)
    {
        int thisSum = 0;
        for (j = i; j < n; j++)
        {
            thisSum += a[j];
            if (thisSum > maxSum){
                left = i;
                right = j;
                maxSum = thisSum;
            }
                
        }
    }
      printfMaxSub(a,left,right); //打印输出

    return maxSum;

}

定义的输出函数如下

// left 子序列的第一个元素下标; right 子序列的最后一个元素下标
void printfMaxSub(int a[],int left,int right)
{
     printf("最大子序列左边的数为 %d  右边的数：%d \n",a[left],a[right]);
    printf("输出最大子序列如下:");
    for(int i = left; i <= right; i++)
    {
         printf(" %d",a[i]);
    }
     printf("\n");
}

第二种O(n)的解法

这个解法巧妙的是if(thisSum < 0){ //和都为负了这里不考虑 thisSum = 0; }的理解

int maxSubSequenceSum (int a[],int len)
{
    int thisSum,MaxSum,j;
    thisSum = MaxSum = 0;
    int left = 0;  //用来记录最大子序列的第一个元素
    int right = 0;  //用来记录最大子序列的最后一个元素
    for(int i = 0; i < len; i++)
    {
        thisSum += a[i];
        if (thisSum > MaxSum ) {
            MaxSum = thisSum;
            right = i;
        }else if(thisSum < 0){ //和都为负了这里不考虑
            thisSum = 0;
        }
        
    }
    
    //求left 最大子序列第一个元素
    int maxTemp = MaxSum;
    for(int i = right; i > 0; i--)
    {
        maxTemp = maxTemp -a[i];
         if( maxTemp > 0){
             printf(" %d",a[i]);
            
         }else if(maxTemp == 0){
            printf(" %d",a[i]);
            left  = i;
             break;
         }
        
    }
     printfMaxSub(a,left,right);
    
    return MaxSum;
}

前两种方法运行的结果如下：

int main()
{
    int a[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4};
    int lengTemp = sizeof(a)/sizeof(*a);
    printf ("MaxSubSum is:%6d.\n", MaxSubSum(a, lengTemp));

    printf("===========================\n");
    printf("maxSubSequenceSum is %d\n",maxSubSequenceSum(a,lengTemp));

    return 0;
}

输出.png

分治法来解

它的思想是：

1.将一个长度为n的序列，一分为二变为两个长度为n/2的子序列，继续将子序列们一分为二，直到每个子序列只含有1个整数。
2.此时问题已经足够小，“最大子序列和”有以下三种情况：左边序列的最大子序列和、右边序列的最大子序列和和处在中间位置上的最大子序列和，我们通过比较，得到三者中的最大值。
3.再将这些“小问题”合并，使用同样的比较方法逐步向上合并这些“左右序列”，直到得到整个序列的最大子序列和，解决问题。`
如下

int getMaxNum(int a,int b,int c){
    
    if (a > b&&a > c){
        return a;
    }
    if (b > a&&b > c){
        return b;
    }
    return c;
}


int maxSubDivide(int data[], int left, int right)
{
    if (right - left == 1){
        //如果当前序列只有一个元素
        return data[left];
    }
    int center = (left + right) / 2;//计算当前序列的分裂点
    int maxLeftSum = maxSubDivide(data,left,center);
    int maxRightSum = maxSubDivide(data,center,right);
    //计算左边界最大子序列和
    int leftBonderSum = 0;
    int maxLeftBonderSum = data[center-1];
    for (int i = center - 1; i >= left; i--){
        leftBonderSum += data[I];
        if (maxLeftBonderSum < leftBonderSum){
            maxLeftBonderSum = leftBonderSum;
        }
    }
    //计算右边界最大子序列和
    int rightBonderSum = 0;
    int maxRightBonderSum = data[center];
    for (int i = center; i < right; i++){
        rightBonderSum += data[I];
        if (maxRightBonderSum < rightBonderSum){
            maxRightBonderSum = rightBonderSum;
        }
    }
    //返回当前序列最大子序列和
    return getMaxNum(maxLeftBonderSum + maxRightBonderSum, maxLeftSum, maxRightSum);
}

前2个方法没考虑全为负数的情况，后面分治法考虑了。细节int maxLeftBonderSum = data[center-1]; int maxRightBonderSum = data[center];这里给的最大值不是0

整体运行如下：

用分治法不知道输出最大连续子序列。

int main()
{
    int a[] = { -2, 1, -3, 4, -1, 2, 1, -5, 4};
    int lengTemp = sizeof(a)/sizeof(*a);
    printf ("MaxSubSum is:%6d.\n", MaxSubSum(a, lengTemp));

    printf("===========================\n");
    printf("maxSubSequenceSum is %d\n",maxSubSequenceSum(a,lengTemp));

    printf("分治法  %d\n",maxSubDivide(a, 0, 9));

    printf("===========================\n");
    int b[]= {-2,-1,-4,-5,-1,-1,-7};
    printf("xxx  %d\n",MaxSubNum(b,0,7));
    printf("分治法  %d\n",maxSubDivide(b, 0, 7));
    return 0;
}

屏幕快照 2019-04-03 下午5.24.31.png