用C语言求最大子序列

给定一整数序列A1, A2,... An (可能有负数),求A1~An的一个子序列Ai~Aj,使得Ai到Aj的和最大

例如:

整数序列-2, 11, -4, 13, -5, 2, -5, -3, 12, -9的最大子序列的和为21。

对于这个问题,最简单也是最容易想到的那就是穷举所有子序列的方法。利用三重循环,依次求出所有子序列的和然后取最大的那个。当然算法复杂度会达到O(n^3)。显然这种方法不是最优的,下面给出一个算法复杂度为O(n)的线性算法实现,算法的来源于Programming Pearls一书。

在给出线性算法之前,先来看一个对穷举算法进行优化的算法,它的算法复杂度为O(n^2)。其实这个算法只是对对穷举算法稍微做了一些修改:其实子序列的和我们并不需要每次都重新计算一遍。假设Sum(i, j)是A[i] ... A[j]的和,那么Sum(i, j+1) = Sum(i, j) + A[j+1]。利用这一个递推,我们就可以得到下面这个算法:

int max_sub(int a[],int size)

{

int i,j,v,max=a[0];

for(i=0;i< FONT>

{

v=0;

for(j=i;j< FONT>

{

v=v+a[j];//Sum(i, j+1) = Sum(i, j) + A[j+1]

if(v>max)

max=v;

}

}

return max;

}

那怎样才能达到线性复杂度呢?这里运用动态规划的思想。先看一下源代码实现:

int max_sub2(int a[], int size)

{

int i,max=0,temp_sum=0;

for(i=0;i< FONT>

{

temp_sum+=a[i];

if(temp_sum>max)

max=temp_sum;

else if(temp_sum<0)

temp_sum=0;

}

return max;

}

在这一遍扫描数组当中,从左到右记录当前子序列的和temp_sum,若这个和不断增加,那么最大子序列的和max也不断增加(不断更新max)。如果往前扫描中遇到负数,那么当前子序列的和将会减小。此时temp_sum 将会小于max,当然max也就不更新。如果temp_sum降到0时,说明前面已经扫描的那一段就可以抛弃了,这时将temp_sum置为0。然后, temp_sum将从后面开始将这个子段进行分析,若有比当前max大的子段,继续更新max。这样一趟扫描结果也就出来了。

内容版权声明:除非注明,否则皆为本站原创文章。

转载注明出处:http://www.heiqu.com/c8f0276055192e00e55043965ce76d21.html