最大子列和求解

题目如下：

四种解题思路对应的完整代码如下：

//最大子列和求解思路

#include<iostream>
#include<cstdio>
using namespace std;
int maxsubseqsum1(int nums[],int size);

int maxsubseqsum2(int nums[],int size);

int maxsubseqsum3(int nums[],int size);

int maxsubseqsum4(int nums[],int size);

void begin();

int main() {
    int switchflag=1;
    while(switchflag==1){
        begin();
        cout<<"输入1继续下一次计算，输入其他按键退出：";
        cin>>switchflag;
    }
    exit(1);
}

void begin(){
    int size,i;
    int maxsum;
    cout<<"请输入整数个数(1-100)：";
    cin>>size;
    while(size<1||size>100) {
        cout<<"请输入1-100范围内的整数：";
        cin>>size;
    }
    int nums[size];
    for(i=0;i<size;i++){
        cout<<"请输入第"<<i+1<<"个整数：";
        cin>>nums[i];
    }
    maxsum = maxsubseqsum1(nums,size);
    cout<<"思路一："<<maxsum<<endl;

    maxsum = maxsubseqsum2(nums,size);
    cout<<"思路二："<<maxsum<<endl;

    maxsum = maxsubseqsum3(nums,size);
    cout<<"思路三："<<maxsum<<endl;

    maxsum = maxsubseqsum4(nums,size);
    cout<<"思路四："<<maxsum<<endl;
} 

//思路一，左边界i，右边界j，确定范围之后，再遍历i...j求和，时间复杂度T(n) =O(n^3)
int maxsubseqsum1(int nums[],int size) {
    int i,j,k;
    int sum,thissum;
    sum=0;
    //子列的左边 0.....size-1
    for(i=0; i<size; i++) {
        //子列的右边 i....size-1
        for(j=i; j<size; j++) {
            thissum=0;
            //循环累加求和i...j
            for(k=i; k<=j; k++) {
                thissum+=nums[k];
            }
            if(thissum>sum) {
                sum=thissum;
            }
        }

    }
    return sum;
}

//基于思路一进行改进，每次右边界右移一个单位时，不再重新开始累加求和，直接在之前的基础上累加，也就是同一个左边界i，对于右边界j右移时，计算一次加法运算即可
//时间复杂度T(n)=O(n^2)
int maxsubseqsum2(int nums[],int size) {
    int i,j;
    int sum,thissum;
    sum=0;
    //子列的左边 0.....size-1
    for(i=0; i<size; i++) {
        //子列的右边 i....size-1
        thissum=0;//同一个左边界i
        for(j=i; j<size; j++) {
            thissum+=nums[j];
            //循环累加求和i...j

            if(thissum>sum) {
                sum=thissum;
            }
        }

    }
    return sum;
}

//返回3个整数中的最大的一个
int getmaxint3(int a,int b,int c) {
    return a>b?(a>c?a:c):(b>c?b:c);
}

//递归调用分治思想的核心代码
int dividegovern(int nums[],int left,int right) {
    //左右最大子列和
    int MaxLeftSum, MaxRightSum;
    
    //跨边界左右最大子列和
    int MaxLeftBorderSum, MaxRightBorderSum;
    
    //当前计算的左右边界子列和
    int LeftBorderSum, RightBorderSum;
    
    int center, i;

    //递归调用终止条件，子列只有一个元素
    if( left == right )  {
        if( nums[left] > 0 )  return nums[left];
        else return 0;
    }

    //先分
    center = ( left + right ) / 2; 
    //递归调用获取左边最大子列和 left.....center 
    MaxLeftSum = dividegovern( nums, left, center );
    
    //递归调用获取右边最大子列和 center+1.....right
    MaxRightSum = dividegovern( nums, center+1, right );

    //跨边界最大子列和 
    MaxLeftBorderSum = 0;
    LeftBorderSum = 0;
    for( i=center; i>=left; i-- ) { /* 从中线向左扫描 */
        LeftBorderSum += nums[i];
        if( LeftBorderSum > MaxLeftBorderSum )
            MaxLeftBorderSum = LeftBorderSum;
    } /* 左边扫描结束 */

    MaxRightBorderSum = 0;
    RightBorderSum = 0;
    for( i=center+1; i<=right; i++ ) { /* 从中线向右扫描 */
        RightBorderSum += nums[i];
        if( RightBorderSum > MaxRightBorderSum )
            MaxRightBorderSum = RightBorderSum;
    } /* 右边扫描结束 */

    /* 下面返回"治"的结果 */
    return getmaxint3( MaxLeftSum, MaxRightSum, MaxLeftBorderSum + MaxRightBorderSum );
}

//思路三，分而治之，先分后治，采用递归的思想
//时间复杂度为T(n)=O(nlogn)
int maxsubseqsum3(int nums[],int size) {
    return dividegovern(nums,0,size-1);
}

//思路四，在线处理
//时间复杂度T(n) =O(n)
int maxsubseqsum4(int nums[],int size) {
    int i,j,k;
    int sum,thissum;
    sum=0;
    //子列的左边 0.....size-1
    for(i=0; i<size; i++) {
        //子列的右边 i....size-1
        for(j=i; j<size; j++) {
            thissum=0;
            //循环累加求和i...j
            for(k=i; k<=j; k++) {
                thissum+=nums[k];
            }
            if(thissum>sum) {
                sum=thissum;
            }
        }

    }
    return sum;
}

最大子列和求解

原文：https://www.cnblogs.com/ericling/p/11773903.html