【算法学习笔记】19.算法设计初步最大子列和问题的几种方法

第一种就是纯粹的暴力枚举起始、终点。 O(n^3)

第二种在第一种的基础上先进行初始化，将以第一个元素为起点，所有元素为终点的所有子列和存储在S数组中，所以在第三层循环中计算子列和是直接用S[j]-S[i-1]即可，这是利用了空间去换时间。O(n^2)

第三种也是O(n^2)，但是在第二种的基础上，要先算出非负数所在的下标从而减少计算和的次数，但是效果并不好。

//算法3 O(n^2)
//主要是想算出正数的地方 从而减少算和的次数，但是需要先找出所有的正数

int n=0,seq[Max_N]={0};//1 for positive or 0  and 0 for negative
int begin=0,end=0;
long max_sum = NULL;
int len = 0;
int pos_list[Max_N]={0};

void getMaxSubSeq(){
    
    if(len==0){//如果全是负数则返回0
        max_sum=0;
        return;
    }else if(len==1){//如果只有一个非负数 返回的就是它
        max_sum=seq[pos_list[0]];
        return;
    }else{//否则我们要对每对儿非负数下标进行计算子列和
        for (int j = 0; j<len; j++) {//j是非负数下标1
            long sum = 0;
            int h = 0;
            for (int k = j+1; k<=len; k++) {//k是非负数下标2
                //下面的for可以改写成S[j]-S[i]的形式从而降低至S[j]-S[i]
                for (int t=pos_list[h]+(h==0?0:1);t<=pos_list[k] ; t++) {
                    sum += seq[t];
                }
                //printf("%d
",int(sum));
                h=k;
                if (max_sum == NULL || max_sum<sum) {
                    max_sum = sum;
                }
                
            }
        }
    }
    
    
}

int main(int argc, const char * argv[]) {
    scanf("%d",&n);
    //input seq
    for (int i = 0; i<n; i++) {
        scanf("%d",&seq[i]);
        if(seq[i]>=0){
            pos_list[len]=i;//把非负数的位置都记下来
            len++;//len是非负数的个数
        }
    }
    getMaxSubSeq();
    cout<<(max_sum)<<endl;
    return 0;
}

第四种利用分治法的思想，先算左面，再算右面（都是递归），再从中间开始向两边延伸。O(nlgn)

//算法4
//分治法 O(nlgn)
//此时计算的是A[m,n)的范围内的最大子序列和
int getMaxSumOfSubSeq(int* A,int x,int y){
    //递归边界
    if(y-x==1)  return A[x];
    //分治第一步，划分（确定子问题）
    int middle = x+(y-x)/2;//此处不用(x+y)/2的原因是想要使middle更加接近左端点
    //分治第二步 递归求解  //利用了>?运算符取两者中较大的
    int maxOfTwoSides = getMaxSumOfSubSeq(A, x, middle) >?
                            getMaxSumOfSubSeq(A,middle , y);
    //分治第三步 合并 求最终解
    int v = 0;//此处v是用来暂时储存连续从中段开始向两边延伸的连续和
    int L=[middle-1],R=A[middle];//从中间开始
    for (int i=middle-1; i>=x; i--)
        L >?= (v+=A[i]);
    v=0;//重复利用临时变量
    for (int i=middle; i<y; i++)//注意不要包括y
        R >?= (v+=A[i]);
    return maxOfTwoSides >? (L+R);
}

第五种，

思路主要是这样的。

在我们用第二种思路时，第二层循环内部要进行比较S[j]-S[i-1]和当前最大和谁大，其实在这个时候，j是一定的，比谁大的本质就是找S[i-1]最小，所以我们不如去维护目前遇到过的最小的S.

int getMSoSS(int* A,int len){
    int index_ofMinS = 0;
    int S[Max_N];
    S[0]=A[0];
    //第一步 先算出最小的S在哪里取得
    //实验表明，如果S[len-1]是最小的 必须用第二小的才行 所以就不算len-1了
    for(int i =1;i<len;i++){
        S[i] = S[i-1]+A[i];
        if(i<len-1 and S[i]<S[index_ofMinS]) index_ofMinS=i;
    }
    //此时已经确定了i-1=index....
    int max_sum=S[0];
    //从此下标之后开始计算~
    for(int j=index_ofMinS+1;j<len;j++){
        //gcc 应该是可以写成 max_sum >?= S[j]-S[index_ofMinS];的呀 奇怪~
        max_sum = max(max_sum , (S[j]-S[index_ofMinS]));
    }
    return max_sum;
}

第六种的伪代码描述：在线处理算法最核心的想法就是当前和如果是负数就不要进行下去因为无论后面是什么，都相当于在做减法，不会比最大和高。

厉害啦，是在线算法，在线算法就是说，任何时候停止输入，得到的都是当前的正确结果，所以应该是线性的O(n)算法。

int MaxSubseqSum4( int A[], int N )  
{   int ThisSum, MaxSum;
    int i;
    ThisSum = MaxSum = 0;
    for( i = 0; i < N; i++ ) {
          ThisSum += A[i]; /* 向右累加 */
          if( ThisSum > MaxSum )
                  MaxSum = ThisSum; /* 发现更大和则更新当前结果 */
          else if( ThisSum < 0 ) /* 如果当前子列和为负 */
                  ThisSum = 0; /* 则不可能使后面的部分和增大，抛弃之 */  
    }
    return MaxSum;  
}

【算法学习笔记】19.算法设计初步 最大子列和问题的几种方法

【算法学习笔记】19.算法设计初步最大子列和问题的几种方法