首页 > 代码库 > 应用实例——最大子列和问题

应用实例——最大子列和问题

2024-09-30 11:09:39   220人阅读

题目描述：给定N个整数的序列{A1,A2,...,AN},求函数f(i,j)=max{0,ΣAk(i<=k<=j)}的最大值

算法1：

 1 int MaxSubseqSum1(int A[],int N){
 2     int ThisSum,MaxSum=0;
 3     int i,j,k;
 4     for(i=0;i<N;i++){//i是子列左端位置
 5         for(j=i;j<N;j++){//j是子列右端位置
 6             ThisSum=0;
 7             for(k=i;k<j;k++){//ThisSum是A[i]到A[j]的子列和
 8                 ThisSum+=A[k];
 9                 if(ThisSum>MaxSum)//如果刚得到的这个子列和更大
10                     MaxSum=ThisSum;//则更新结果
11             }
12         }
13     }
14     return MaxSum;
15 }

由程序结构可知，此算法的时间复杂度T(N)=O(N3)[有三层嵌套的for循环]

算法2：

 1 int MaxSubseqSum1(int A[],int N){
 2      int ThisSum,MaxSum=0;
 3      int i,j;
 4      for(i=0;i<N;i++){//i是子列左端位置
 5          ThisSum=0;
 6          for(j=i;j<N;j++){//j是子列右端位置
 7              ThisSum+=A[j];//对于相同的i，不同的j，只要在j-1次循环的基础上累加1项即可
 8                  if(ThisSum>MaxSum)//如果刚得到的这个子列和更大
 9                     MaxSum=ThisSum;//则更新结果
10              }
11          }
12     }
13     return MaxSum;
14 }

由程序结构可知，此算法的时间复杂度T(N)=O(N2)[有两层嵌套的for循环]

算法3：分而治之

算法思路：将一个比较大而复杂的问题切分成比较小的模块，然后分头解决，最后把结果合并起来。

工作流程：[假设待解决的问题放在一个数组里面]

  • 第一步：划分：按照平衡子问题的原则，将序列(a1,a2,...,an)划分成长度相同的两个序列(a1,...,an/2)和(an/2+1,...,an),则会出现一下三种情况：
    • a1,...,an的最大字段和=a1,...,an/2的最大字段和①
    • a1,...,an的最大字段和=an/2+1,...,an的最大字段和②
    • a1,...,an的最大字段和=Σak(i<=k<=j)，且1<=i<=n/2,n/2+1<=j<=n③
  • 第二步：求解子问题：对于划分阶段的情况①和②可递归求解，情况③需要分别计算左右两端的最大子列和，然后两个之和为情况③的最大子列和。
  • 第三步：合并：比较在划分阶段三种情况下的最大子列和，取三者关系中的较大者为原问题的解。

     技术分享

例：给定一个数组[4,-3,5,-2,-1,2,6,-2]

先从中间将其一分为二

技术分享

然后递归地先解决左半边，继续将其一分为二

技术分享

继续地递归到左半边，继续分

技术分享

针对最后的一次划分，左边的最大子列和为4，右边最大子列和为-3,小于左边，会返回0，则跨越边界的最大子列和为4。依此类推，得到最终的划分结果为：

技术分享

int MaxSubseqSum3(int a[],int left,int right){//求序列a[left]~a[right]的最大子列和
    int sum=0,midSum=0,leftSum=0,rightSum=0;
    int center,s1,s2,lefts,rights;
    if(left==right)//如果序列长度为1，直接求解
        sum=a[left];
    else{
        center=(left+right)/2;//划分
        leftSum=MaxSubseqSum3(a,left,center);//对应情况①，递归求解
        rightSum=MaxSubseqSum3(a,center,right);//对应情况②，递归求解
        s1=0;lefts=0;//以下对应情况③，先求解s1
        for(int i=center;i>=left;i--){
            lefts+=a[i];
            if(lefts>s1)
                s1=lefts;
        }
        s2=0;rights=0;//再求解s2
        for(int j=center+1;j<=right;j++){
            rights+=a[j];
            if(rights>s2)
                s2=rights;
        }
        midSum=s1+s2;//计算情况③的最大子列和
        if(midSum<leftSum)//合并解，取较大者
            sum=lefstSum;
        else 
            sum=midSum;
        if(sum<rightSum)
            sum=rightSum;
    }
    return sum;
}

划分之后，每个程序执行的数据规模是N/2，对应划分得到的情况①和情况②，需要分别进行递归求解，对应情况③，两个并列for循环的时间复杂性是O(N)，所以存在如下的递推式：

  • T(N)=1          当N=1时；
  • T(N)=2T(N/2)+c·N   当N>1时；

T(N)=2T(N/2)+c·N=2[2T(N/4)+c·N/2]+c·N

   =22T(N/22)+2c·N

   =2kO(1)+ck·N,其中N/2k=1

   =O(Nlog2N)

由程序结构可知，此算法的时间复杂度T(N)=O(Nlog2N)

算法4：在线处理

 “在线”的意思是指每输入一个数据就进行即时处理，在任何一个地方中止输入，算法都能正确给出当前的解。

 1 int MaxSubseqSum4(int A[],int N){ 2     int ThisSum,MaxSum=0;
 3     int i;
 4     ThisSum=MaxSum=0;
 5     for(i=0;i<N;i++){
 6         ThisSum+=A[i];//向右累加
 7         if(ThisSum>MaxSum)
 8             MaxSum=ThisSum;//发现更大和则更新当前结果
 9         else if(ThisSum<0)//如果当前子列和为负
10             ThisSum=0;//则不可能使得后面的部分和增大，抛弃之
11     }
12     return MaxSum;
13 }

 由程序结构可知，此算法的时间复杂度T(N)=O(N)[只有一个for循环，而且if-else的复杂度都为常数]

复杂度越小，理解起来越困难

例：

技术分享

 ①第一个数字为-1，由于它不能使后面的部分增大，因此将ThisSum重置为0，MaxSum=0

技术分享

②MaxSum=3,ThisSum=3

技术分享

③ThisSum=1>0，不会被重置为0

技术分享

④ThisSum=5,MaxSum=5,最大和更新

技术分享

⑤ThisSum=-1<0，被抛弃，将ThisSum重置为0

技术分享

⑥ThisSum=1,MaxSum=5

技术分享

 ⑦ThisSum=7,MaxSum=7，最大和更新

技术分享

 ⑧ThisSum=6,MaxSum=7,最大和未改变

所以得到的最大子列和为7。

运行时间比较(秒)
算法 1 2 3 4
时间复杂度 O(N3) O(N2) O(NlogN) O(N)
N=10 0.00103 0.00045 0.00066 0.00034
N=100 0.47015 0.01112 0.00486 0.00063
N=1000 448.77 1.1233 0.05843 0.00333
N=10000 NA 111.13 0.68631 0.03042
N=100000 NA NA 8.0113 0.29832

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 


 

 

应用实例——最大子列和问题


联系
我们