欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

最大子序列和问题

程序员文章站 2022-05-29 12:04:48
本周学习陈越老师的数据结构课程时,约到最大子序列和的问题。趁着周末有空,把脑海中还有的记忆整理下。 最大子序列和问题:给定一个由N个整数组成成的序列{A1,A2,...,AN},求函数f(i,j)=max{0,Σjk=iAk}的最大值。 第一种方法可以用枚举法,把所有的可能的组合都遍历一遍。 把所有 ......

  本周学习陈越老师的数据结构课程时,约到最大子序列和的问题。趁着周末有空,把脑海中还有的记忆整理下。

  最大子序列和问题:给定一个由n个整数组成成的序列{a1,a2,...,an},求函数f(i,j)=max{0,σjk=iak}的最大值。

  第一种方法可以用枚举法,把所有的可能的组合都遍历一遍。

#include <stdio.h>
#include <iostream>
using namespace std;

int maxsubsum(int a[], int n){
    int i, j, k, sum, maxsum = 0;
    for( i = 0; i<n; i++){//子序列左端
        for( j = i; j<n; j++){//子序列右端
            sum=0;//初始化子序列和
            for (k= i; k<j; k++){
                sum+=a[k];//求得子序列和
            }
            if(sum>maxsum){//对比子序列和
                maxsum=sum;//更新子序列和
            }
        }
    }
    return maxsum;   
}

int main(){
    int n, i = 0;
    scanf("%d\n",&n);//数组长度
    int a[n];
    for ( i= 0; i<n; i++){//输入数组
        scanf("%d",&a[i]);
    }
    printf("\n%d",maxsubsum(a,n));
    return 0;
}

  把所有可能都求出来然后相加,时间复杂度为o(n3)。在该方法上改进,对于左端相同(即i相同)右端不同(即j不同)的子序列的和,只需要在前一项的结果加上当前的右端a[j]即可。

#include <stdio.h>
#include <iostream>
using namespace std;

int maxsubsum(int a[], int n){
    int i, j, k, sum, maxsum = 0;
    for( i = 0; i<n; i++){//子序列左端
        sum=0;//初始化子序列和
        for( j = i; j<n; j++){//子序列右端
            sum+=a[j];//相同的i,不同j的子序列的和,只需要在上一次的结果上累加即可
        }
        if(sum>maxsum){//对比子序列和
            maxsum=sum;//更新子序列和
       }
   }
    return maxsum;   
}

int main(){
    int n, i = 0;
    scanf("%d\n",&n);//数组长度
    int a[n];
    for ( i= 0; i<n; i++){//输入数组
        scanf("%d",&a[i]);
    }
    printf("\n%d",maxsubsum(a,n));
    return 0;
}

  改进后,时间复杂度为o(n2)。

  第二种方法,可以用分治法;分治法:把问题分解为小的子问题解决,然后把解决的子问题合并得出原问题的答案。再最大子序列问题中算法思路是:

  (1)把原序列一份为二,分解为左右大小分别为(n/2)大小的序列;

  (2)变为求解左右两个序列的最大子序列问题,和解跨越两个子序列边界的最大子序列问题;

  (3)求解左右两个子序列值时,按(1)(2)步骤重复,直到不能再划分为二,此时,子序列为a[i],为一个元素;

  (4)把所有子问题答案整合,即为原问题的最大子序列答案。

#include <stdio.h>
#include <iostream>
using namespace std;

int max(int a, int b, int c){//求最大整数
    int max=a;
    if(b>max){
        max=b;
    }
    if(c>max){
        max=c;
    }
    return max;
}

int maxsubsum(int a[], int left, int right){
    int maxleftsum, maxrightsum, 
    maxleftbordersum, maxrightbordersum,
    leftbordersum, rightbordersum;

    if(left == right)
        if(a[left]>0)
            return a[left];
        else
            return 0;

    int center, i;

    center = (left+right)/2;//分界线
    maxleftsum = maxsubsum(a, left, center);
    maxrightsum = maxsubsum(a, center+1, right);//递归求左右两边子列的最大子列和

    maxleftbordersum = 0, leftbordersum=0; 
    for ( i = center; i>=left; i--){
        leftbordersum+=a[i];
        if(leftbordersum>maxleftbordersum){
            maxleftbordersum=leftbordersum;
        }
    }//向左扫求跨边界的最大子列和
    
    maxrightbordersum = 0, rightbordersum=0;
    for ( i = center+1; i<=right; i++){
        rightbordersum+=a[i];
        if(rightbordersum>maxrightbordersum){
            maxrightbordersum=rightbordersum;
        }
    }//向右扫求跨边界的最大子列和

    return max(maxleftsum, maxrightsum, maxleftbordersum+maxrightbordersum);//返回左右子列,和跨边界子列中最大的子列和
}

int main(){
    int n;
    scanf("%d\n",&n);
    int a[n];
    for (int i= 0; i<n; i++){
        scanf("%d",&a[i]);
    }
    int right = n-1, left=0;
    printf("\n%d",maxsubsum(a,left,right));
    system("pause");
    return 0;
}

  这个算法总的时间复杂度的递推公式:t(n)=2*t(n/2)+c*n; t(n/2)=2*(n/4)+c*(n/2).........t(1)=o(1) ;t(n)=2k*o(1)+c*kn, 2k=n; t(n)=o(n)+o(n*logn);该算法时间复杂度为n*logn。

  第三种算法是在线处理法。该算法的思路是:

  (1)先给最大子序列和初始化为0

  (2)从左往右逐项累加求和;

  (3)把(2)中逐项累加的和与已有的最大子序列和对比,若当前和比最大子序列和大,则把值赋予最大子序列;

  (4)若当前和为负,则可以判断其与后面任何项相加,都会使其变小,因此,舍去前面的项,把当前和归0;

  (5)重复(2)-(4)得到最大子列和。

#include <stdio.h>
#include <iostream>
using namespace std;

int maxsubsum(int a[], int n){
    int i, maxsum = 0, sum = 0;//给maxsum设置一个小值
    for (i = 0; i<n; i++ ){
        sum += a[i];  //逐项相加
        if(sum>maxsum){
            maxsum = sum; //如果当前的子项的和大于maxsum,把当前子项的和sum代入
        }
        else if (sum<0){
            sum = 0;//若当前子项和小于0,则归零从当前项开始重新累加
        }
    }
    return maxsum;
}

int main(){
    int n;
    scanf("%d\n",&n);
    int a[n];
    for (int i= 0; i<n; i++){
        scanf("%d",&a[i]);
    }
    printf("\n%d",maxsubsum(a,n));
    system("pause");
    return 0;
}

该算法时间复杂度为o(n)。但当整个序列都不为正数时,给出答案会是0,很明显是不正确的;因此可以做下改进,得到:

#include <stdio.h>
#include <iostream>
using namespace std;

int maxsubsum(int a[], int n){
    int i, k = 0, maxsum = 0, sum = 0;//给maxsum初始化为0
    
    for(i= 0; i<n; i++){ //判断整个序列是否都不大于0
       if(a[i]>0){
           k=1;
       } 
    }
    
    if(k){
        for (i = 0; i<n; i++ ){
            sum += a[i];  //逐项相加
            if(sum>maxsum)
                maxsum = sum; //如果当前的子项的和大于maxsum,把当前子项的和sum代入
            else if (sum<0)
                sum = 0;//若当前子项和小于0,则归零从当前项开始重新累加         
        }
    }
    else{
        maxsum = a[0];
        for (i = 0; i<n; i++ ){
            if(a[i]>maxsum)
                maxsum = a[i]; //当整个序列都不为正时,最大子序列也就是其序列元素中的最大值
        }
    }

    return maxsum;
}

int main(){
    int n;
    scanf("%d\n",&n);
    int a[n];
    for (int i= 0; i<n; i++){
        scanf("%d",&a[i]);
    }
    printf("\n%d",maxsubsum(a,n));
    system("pause");
    return 0;
}