最大子数列和

最大子数列和问题

问题提出

请用分治法求数列的最大子段和。给定 n 个元素的整数列（可以包含负数）$a_1,a_2,\ldots,a_n$。求形如：

$$a_{i},a_{i+1},\ldots,a_{j},i,j=1,\ldots,n,i \leq j$$

的子段，使其和为最大。当所有整数均为负整数时定义其最大子段和为0。如:

$（a_1,a_2,a_3,a_4,a_5,a_6）=（-2,11,-4,13,-5,-2）$时，最大子段和为：$a_2+a_3+a4=11-4+13=20$

给定 n 个元素的整数列（可以包含负数） $a_{1},a_{2},\ldots,a_{n}$ 。求形如：

$$a_{i},a_{i+1},\ldots,a_{j}, i,j = 1,\ldots,n,i \leq j$$

的子段，使其和为最大。当所有整数均为负整数时定义其最大子段和为0。如 $(a_{1},a_{2},a_{3},a_{4},a_{5},a_{6}) = (-2,11,-4,13,-5,-2)$ 时，最大子段和为：

$$a_{2}+a_{3}+a_{4} = 11 - 4 + 13 = 20$$

分治法求解

问题分析：

求解n个元素的整数列的子数列和的最大值问题，可以分解为以下三种情况：

• 最大子数列和在数列的左半部分
• 最大子数列和在数列的右半部分
• 最大子数列和由跨越中间界的左右两部分最大和相加而成

故问题可利用分治法对原问题进行求解

计算模型

• 定义存储n个整数元素的数组为 $a[i] ,0 \leq i \leq n-1$

• 左半部分的最大子数列和为maxLeft

• 右半部分的最大子数列和为maxRight

• 跨边界的最大子数列和为maxBorder
• 最大子列和maxSum为maxLeft、maxRight、maxBorder中的最大值

$$\left\{\begin{array}{a} mid &= (low+high) / 2 \\ maxLeft &= MaxSubsum(low,mid,a[]) \\ maxRight &= MaxSubsum(mid+1,high,a[]) \\ maxBorder &= GetBordersum(mid,a[]) \\ maxSum &= \max({maxLeft,maxRight,maxBorder}) \end{array}\right.$$

边界和的求法伪代码描述为：

leftmaxsum = 0, rightmaxsum = 0
for i = center downto 0
  leftsum += a[i]
  if leftsum > leftmaxsum
    leftmaxsum = leftsum
for j = center to high
  rightsum+= a[j]
  if rightsum > rightmaxsum
    rightmaxsum = rightsum 
return leftmaxsum+rightmaxsum

时间复杂度分析

设问题规模为n，则有：

• 左右部分的问题规模为 $\frac{n}{2}$
• maxBorder的计算主要为两个for循环，其循环总次数与 $high-low$相当的，因此

$$T(n) = 2T(\frac{n}{2}) + O(n)$$

由主定理，$a=2,b=2,f(n)=O(n)$

$n^{log_{2}2}=n=O(n)$

符合主定理的第二种情况：

$$T(n)=\Theta(n*log_{2}n)=\Theta(nlog_{2}n)$$

算法实现(自主完成)

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 20

int MaxOfThreeNumber( int A, int B, int C )
{ 
    return A > B ? A > C ? A : C : B > C ? B : C;
}

int GetBorderSum(int center,int high,int a[])
{
    int left_border_sum = 0, right_border_sum = 0;   //跨边界的和
    int left_store_sum = 0, right_store_sum = 0;
    for (int i = center; i>=0; --i)
    {
        left_store_sum += a[i];
        if (left_border_sum < left_store_sum) left_border_sum = left_store_sum;
    }
    for(int i = center+1; i<=high; ++i)
    {
        right_store_sum += a[i];
        if(right_border_sum < right_store_sum) right_border_sum = right_store_sum;
    }
    return left_border_sum + right_border_sum;
}


int MaxSubsum(int a[], int low, int high)
{
    if(low == high)
    {
        if (a[low]) return a[low];
        else return 0;
    }
    
    int max_left = 0,max_right = 0,max_border = 0;  //左右部分的最大子列和    
    int center = ( low + high ) / 2;
    max_left  = MaxSubsum(a, low, center);
    max_right = MaxSubsum(a, center+1, high);
    max_border = GetBorderSum(center, high, a);
    
    
    return MaxOfThreeNumber(max_left, max_right, max_border);
}

int main(int argc, const char * argv[])
{
    srand((unsigned)time(NULL));
    int nums[N];
    int i = 0;
    for(i=0;i<N;++i)
    {
        nums[i] = rand()%(100+1);
        if (nums[i] % 2 == 0) nums[i] = -nums[i];
    }
    for (i=0; i<N; ++i) printf("%d ",nums[i]);
    time_t start,end;
    start = clock();
    int max = MaxSubsum(nums,0, N-1);
    printf("\nmax=%d",max);
    end = clock();
    printf("\ncost time= %lf\n",(double)(end-start)/CLOCKS_PER_SEC);
    
    return 0;
}

算法测试

线性时间解法

计算模型

在计算最大子列和时，当发现目前计算的子列和小于零，则舍弃这一部分子列和，

算法时间复杂度

由于仅循环遍历一次整数列即可得出最大子列和，故有：

$$T(n) = \Theta(n)$$

int maxsubsquence3(int a[], int n)
{
    int store_sum = 0,max_sum = 0;
    int i;
    for (i = 0; i<n; ++i)
    {
        store_sum += a[i];
        if(max_sum < store_sum) max_sum = store_sum;
        if (store_sum < 0) store_sum =0;
    }
    return max_sum;
}