最大子段和问题5种算法

〖题目描述〗 在一个一维数组里找出连续的几个数,使数的总和最大。

  
取出所给序列的所有子序列求和,先分n组比较这n(n＋1)/2个序列的和，再将每组的最大值比较，从而得到最大值以及其上下标。

a₁                        a₂                              a_n-1         a_n
a₁+a₂                  a₂+a₃                       a_n-1+a_n 
a₁+a₂+a₃           a₂+a₃+a₄        ......
......                     ......
a₁+a₂......+a_n       a₂+a₃......+a_n

此算法比较直接，也容易写出代码，但其时间开销为O(n²)，空间开销为O(n)，效率不高。

现在想出来的算法时间代价是O(n),空间代价是常数(主要指辅助空间的开销，而a1a2......an的开销不算在内)。
当然此算法每上一个算法那么直接，写代码也麻烦一些，具体如下：
1. 从左向右寻找在序列中出现的第一个非负整数，如果找不到即全为负数，返回最大序列值为0，否则执行2。
2. 将起下标赋给besti，并将第besti个数作为最大子序列和S的初值。
3. 下游标k的初值为besti＋1，下游k寻找到下一个非负整数，计算besti到k子段的值记为S_ik。
4. 比较S，S_ik以及第k个整数的值：当S最大时，将besti赋值给下标bestj；当S_ik最大时，将S_ik赋值给S，将k赋值给下标bestj；当第k个整数的值最大时，其值赋给S，besti的值改写为k，将besti的值赋给bestj。
5.下游k，如果k<=n,转从3开始执行,否则返回最大子序列和S,算法结束。

第二种算法的实现代码

http://hi.baidu.com/longchengjiang/blog

#include<iostream.h>
#define sum 21
int b[sum];
//算法1
int MAX_SUM(int a[])
{
int max,i,j,k,k1;
k1=0;
for(i=0;i<=5;i++) //进行3重循环，计算出所有可能的子段和

{
for(j=i;j<=5;j++)
{
      
   for( k=i;k<=j;k++)
   {
    b[k1]+=a[k];
   }
   if(b[k1]<0)
    b[k1]=0;
   k1++;
}
}
max=b[0];
for(k1=1;k1<sum;k1++) //求出数组b中的最大值，即为所求的最大子段和

if(max<b[k1])
max=b[k1];
return max;
    
}
//算法2
int MAX_SUM(int a[])
{
int k=0,max;
for(int i=0;i<=5;i++) //进行2重循环计算可能的最大子段和，存于辅助数组b中

{
for(int j=i;j<=5;j++)
{
   if(i==j)
    b[k]=a[j];
   else
    b[k]=b[k-1]+a[j]; //利用前k-1个已计算出的最大子段和求k个的最大子段和

   if(b[k]<0)
    b[k]=0;
   k++;
}
    max=b[0];
for(k=1;k<sum;k++) //求出数组b中的最大值，即为所求的最大子段和

if(max<b[k])
max=b[k];
return max;
}
}
//算法3
int MAX_SUM(int a[], int left, int right)
{
int leftsum,rightsum,center,s1,s2,lefts,rights,s;
if (left==right) //当left==right时，直接计算最大子段和

    {if (a[left]>0)
return a[left];
     else return 0;}
else
{
    center=(left+right)/2;
    leftsum=MAX_SUM(a,left,center); //否则计算当前子段[1..n/2]的最大子段

    rightsum=MAX_SUM(a,center+1,right); //否则计算当前子段[n/2+1..n]的最大子段

}
s1=0;lefts=0;
for(int i=center;i>=left;i--) //计算前半段子段和

{
     lefts+=a[i];
if(lefts>s1) //如果子段和小于0，记为0

   s1=lefts;
}


s2=rights=0;
for(int j=center+1;j<=right;j++) //计算后半段子段和

{
   rights+=a[j];
if(rights>s2)
   s2=rights;
}
s=s1+s2; //计算跨越2子段的子段和s

if(s>leftsum) //前半段leftsum，后半段rightsum，和s的大小，最大者即是

                           //  当前段的最大子段和
{
if(s>rightsum)
return s;
else
return rightsum;
}
else
{
if(leftsum>rights)
return leftsum;
else
return rightsum;
}
}


//算法4
int MAX_SUM(int a[]) //根据推导b[j]等于a[0..j]的最大子段和

{
int temp,max;
int b[6]; //辅助数组b，存储b[1..5]的各个子段和

for(int j=0;j<=6;j++)
{
if(j==0)
   b1[j]=0; //b[0]定为不包含任何元素的子段，显然它为0

else
{
   temp=b1[j-1]+a[j-1]; //计算b[j]的值。b[j]将等于b[j-1]和a[j]中较大的那个

   if(temp<a[j-1])
    b1[j]=a[j-1];
   else
    b1[j]=temp;
}
}
max=b1[1];
for(j=2;j<=6;j++) //计算b[1..6]的最大值，即为所求的最大子段和

{
if(max<b1[j])
   max=b1[j];
}
return max;
}

//算法5，其实用代码实现并不难，难的是思想。

int MAX_SUM(int a[],int i,int j)
{
int k,s1,l,temp; //s1用来存储当前子段的s[i,l-1]的最大子段和

s1=0;temp=0; //temp用来与s1比较，判断是否此时的s1是最大子段

for(l=i;l<=j;l++)
{
temp=temp+a[l];
if(temp>=s1)
   s1=temp;
else
   if(temp<=0) //当temp小于等于0，找到l的值，跳出循环

   {
    break;
   }
}
if(l>=j) //如果l等于j，或者l等于j+1，则s[i,l-1]的最大子

            // 段s1就是s[i,j]的最大子段和
return s1;
if(l==i) //如果l等于i，则最大子段在s[i+1,j],递归计算。

                          // 问题规模减少1。
return MAX_SUM(a,l+1,j);
else //如果i
         //间更大的那个。其中s[i,l-1]的最大子段就是s1
return MAX(s1,MAX_SUM(a,l+1,j));
}

#include<iostream.h>
void main()
{
int n,i,j;
int MaxSum(int n, int* a, int& besti, int& bestj);
    
cout<<"输入序列长度(必须为正整数):"<<endl;
cin>>n;

int* a=new int[n];
    
cout<<"输入"<<n<<"个整数："<<endl;
for(i=0;i<n;i++)
   cin>>a[i];
    
int S=MaxSum(n,a,i,j);
cout<<endl<<"输出结果："<<endl;
cout<<"i="<<i<<endl<<"j="<<j<<endl<<"最大子段和："<<S<<endl;
delete []a;
}


int MaxSum(int n, int* a, int& besti, int& bestj)
{
bestj=besti=0; //初始化上下标

int k=besti+1; //初始化子段的下游标

int Sik=0;

while(a[besti]<0 && besti<n) besti++; //寻找第一个非负整数

if(besti==n) return 0; // 如果全部是负数，返回最大子段值为0

int S=a[besti];//当前最大子段和


while(k<n){ //当下游标k＝n时结束

   while(a[k]<0 && k<n) k++;//寻找下一个非负整数

   //计算i—k子段的和

   Sik=0;
   for(int i=besti; i<=k; i++ )
       Sik += a[i];
//下面的3个分之语句为此算法的关键

   if(a[k]>=Sik && a[k]>=S) //下游标对应的值最大时

   {
    bestj=besti=k; //当前所求的子段上下标均为k

    S=a[k];//当前所求子段和为a[k]

   }
   else if(Sik>=a[k] && Sik>=S)//i—k子段的和最大时

   {
    S=Sik; //当前所求子段和为

    bestj=k; //当前所求子段下标为k

   }
   else if(S>=a[k] && S>=Sik) bestj=besti; //当前最大子段和为a[besti],下标为besti


   k++;//下游标继续下游

}

return S;//返回非0的最大子段和

}

//atlantis 的代码，基本思想就是正数、负数序列分别求和，一遍扫描完成。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

template <class T>
struct result_node {
    size_t start;
    size_t end;
    T value;
};

struct result_max {
    bool operator() (const result_node<int> x,
                     const result_node<int> y) const {
        return x.value < y.value;
    }
};

template <class T>
void maxSubQueue(vector<T> ia, vector<result_node<int> >& aVector, size_t n)
{
    size_t itor = 0;
    int postSeq = 0;
    int negSeq = 0;
    int StartIndex = 0;
    int LastIndex = 0;
    result_node<int> rn;

    while (itor != n) {
        while(itor != n && ia[itor] < 0)
            negSeq += ia[itor++];
        if (postSeq + negSeq < 0) {
            StartIndex = LastIndex = itor;
            postSeq = negSeq = 0;
            continue;
        }
        else postSeq += negSeq;

        while(itor != n && ia[itor] >= 0)
            postSeq += ia[itor++];
        LastIndex = itor-1;

        if (StartIndex <= LastIndex) {
            rn.start = StartIndex;
            rn.end = LastIndex;
            rn.value = postSeq;
            aVector.push_back(rn);
        }
    }
}
int main() {
    int seq[] = {-2, 2, 3, 8, -5, -7, 5, 14, -21, 13, 6, 23, -41, 43};
    vector<int> ia(seq, seq+14);
    vector<result_node<int> > aVector;

    maxSubQueue(ia, aVector, ia.size());
    result_node<int> rn = (*max_element(aVector.begin(), aVector.end(), resu
lt_max()));
    cout << rn.start << " " << rn.end << " " << rn.value;
    return 0;
}