GroupBlog

算法设计与分析-----求最大字段和问题

问题描述:给定由n个整数组成的序列(a1,a2,a3......,an),求该序列的子段的最大值.

常规法:

从a1开始，求出以a1开头的子序列最大的和为sum，依次从a2开始,在sum等于以a1开头的基础上,与以a2开头的不同长度的子序列进行比较，取最大值,然后依次从a3,a4......an开头，最后得到最大子序列的和;

int  maxSum(int a[],int n)
{
    int ThisSum,MaxSum=0,i,j,k;
    for(i=0;i<n;i++){
        ThisSum=0;
        for(j=i;j<n;j++){
            ThisSum+=a[j];
            if(ThisSum>MaxSum){
                MaxSum=ThisSum;  //每一趟的最大值
            }
        }
    }
    return MaxSum;
}

分治法:

用分治法求最大字段和首先将问题划分,即将一个整序列划分成长度相等的两个序列，这时会出现3种情况，即1，最大字段和在第一个序列, 2最大字段和在第二序列，3，最大字段和在第一个序列和第二个序列之间.然后将这3中情况的最大字段合并，取3者之中的最大值为问题的解.

int Max3(int a,int b,int c)  //求三种情况下的最大值;
{
    int max =a;
    if(max < b) max=b;
    if(max < c) max=c;
    return max;
}
int MaxSubSum(int *a,int fI,int lI)
{
    int i=0;
    int mI=(fI+lI)>>2;   //右移相当于除于2，左移相当于乘于2;
    int lMax=0,rMax=0,lMaxBorder=0,rMaxBorder=0,lSumBorder=0,rSumBorder=0,max=0;
    if(fI==lI){
        return *(a+fI);
    }
    lMax=MaxSubSum(a,fI,mI);  //对应情况1，递归求解
    rMax=MaxSubSum(a,mI+1,lI); //对应情况2，递归求解
    for(i=mI;i>=fI;i--){   //求左边界的最大字段和;
        lSumBorder+=*(a+i);
        if(lMaxBorder < lSumBorder){
            lMaxBorder=lSumBorder;   //包括左边界的最大值放在lMaxBorder
        }
    }
    for(i=mI+1;i<=lI;i++){   //求右边界的最大字段和;
        rSumBorder+=*(a+i);
        if(rMaxBorder < rSumBorder){
            rMaxBorder=rSumBorder;
        }
    }
    max=Max3(lMax,rMax,lMaxBorder+rMaxBorder);
    return max;
}

动态规划法

设All[i]为子问题A[i...n-1]的连续子序列之和的最大值,start[i]为从A[i]开始的连续之和的最大值,因此:

All[i]=A[n-1] ,当i=n-1时；

All[i]=max{All[i+1],start[i]} i=0,1,2....n-2;

其中start[i]为:

start[i]=A[n-1],当i=n-1时;

start[i]=max{A[i],A[i]+start[i+1]} i=0,1,2,3.....n-2;

代码如下:

int max(int a, int b)  
    {  
        return a > b ? a:b;  
    }    
  int maxSum(int A[], int n)  
    {  
        int All[n], start[n], i;  
        start[n - 1] = All[n - 1] = A[n - 1];  
        for (i = n - 2;i >= 0;i--)  
        {  
            start[i] = max(A[i], A[i] + start[i + 1]);  
            All[i] = max(All[i + 1], start[i]);  
        }  
        return All[0];  
    }

下面是对空间复杂度的优化:

  int max(int a, int b)  
{  
    return a > b ? a:b;  
} 
  int maxSum(int A[], int n)  
    {  
        int start, All, i;  
        start = All = A[n - 1];  
        for (i = n - 2;i >= 0;i--)  
        {  
            start = max(A[i], A[i] + start);  
            All = max(All, start);  
        }  
        return All;  
    }

时间复杂度为 O(n);

算法设计与分析-----求最大字段和问题

常规法:

分治法: