查找数组最大子序列和

/*以下代码皆为原创，版权归作者本人所有，转载请标明出处并通知作者，否则必追究责任*///Author: To_Sky// 问题：找出一个数组中最大子序列和，并返回子序列范围
// 思路：此题有很多种方法，常用的是穷举，归并，以及今天我写的这种算法
// 同其他算法相比该方法属于联机算法，并且复杂度较低。该算法统一用C++模板实现
#include <iostream>
using namespace std;
//返回值第一个数为起始位置，第二个数为末尾位置，第三个值为最大子和
template<typename T> int * findMaxSeq(T *arr,int len){
    int note=0,max=0;
    int flag=0,start1=0,start2=0,end1=0;
    for(int i=0;i<len;i++){
        note+=arr[i];
        if(note<0){
            flag=1;
            start2=i+1;
            note=0;
        }
        int temp=(max>note)?max:note;
        if(temp!=max){
            if(flag){
                start1=start2;
                flag=0;
            }
           end1=i;
        }
        max=temp;
    }
    int *res=new int[3];
    res[0]=start1;
    res[1]=end1;
    res[2]=max;
    return res;
}
int main(){
    int arr[]={2,3,-1,9,-20,1,4,7,11,-1,3,-7,2,4};
    int *res=findMaxSeq(arr,14);
    cout<<"最大子序列范围为："<<res[0]<<"到"<<res[1]<<endl;
    cout<<"最大和为:"<<res[2];
    return 0;
}

运行结果：
最大子序列范围为：5到10
最大和为:25

以上代码不支持全负数，因为全部为负数时候，没有多大意义。最大子序列即为最大值。以上代码皆为原创，转载请标明出处并通知作者。
原文链接: https://www.cnblogs.com/siubr/archive/2012/10/18/2730168.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍