1.1 最大子序列求和

川长思鸟来 2022-06-04 09:15 135阅读 0赞

*  题目大意：给出一序列，求该序列的子序列和最大的子序列。
 *  下面共有四种算法：程序运行时间依次降低，最佩服的是最后的联机算法，时间已达到O(N).
 *  注意C++中的函数调用与传值
 *  下面分析四种算法：关于每种程序的运行时间，我们只关注他的最坏情况即可。
    
     *  算法一，有三个大循环，假设第一个循环的大小N,每个循环都考虑最坏的情况，则总数为 O（N），  
        使用开销的思路推一下，精确分析可知，最大开销: ∑N−1i=0∑N−1j=i∑jk=i1,该和指出此程序三次循环被执行了多少次，由内到外求值，首先我们有  
        
        
        ∑k=ij1=j−i\+1
        
          
        然后我们可以得到  
        
        
        ∑j=iN−1(j−i\+1)=(N−i\+1)(N−i)2
        
          
        继续：  
        
        
        ∑i=0N−1(N−i\+1)(N−i)2=∑i=1N(N−i\+1)(N−i\+2)2
        
          
        
        
        =12∑i=1Ni2−(N\+32)∑i=1Ni\+12(N2\+3N\+2)∑i=1N1
        
          
        
        
        =12N(N\+1)(2N\+1)6−(N\+32N(N\+1)2\+N2\+3N\+22N)
        
          
        
        
        =N3\+3N2\+2N6
        
          
        所以算法一的最大消费为O（N3）。

#include<iostream>
     #include<vector>
     #include<algorithm>
     using namespace std;
    //最大子序列求和
    //算法一
    //穷举法
    int maxsubsum(const vector &a)
    {
        int maxsum=0;
        for(int i=0;i<a.size();i++)
         for(int j=i;j<a.size();j++)
        {
            int ThisSum=0;
            for(int k=i;k<=j;k++)
            {
                ThisSum+=a[k];
            }
            if(ThisSum>maxsum)
                maxsum=ThisSum;
        }
        return maxsum;
    }
    //算法二
    //对穷举法进行优化
    int maxsubsum1(const vector &a)
    {
        int maxsum=0;
        for(int i=0;i<a.size();i++)
        {
            int ThisSum=0;
            for(int j=i;j<a.size();j++)
            {
                ThisSum+=a[j];
                if(ThisSum>maxsum)
                maxsum=ThisSum;
            }
        }
        return maxsum;
    }
    //算法三
    //分治法
    int maxsumrec(const vector<int> &a,int left,int right)
    {
        if(left==right)
        {
            if(a[left]>0)
                return a[left];
            else
                return 0;
        }
        int center=(left+right)/2;
        int maxleftsum=maxsumrec(a,left,center);
        int maxrightsum=maxsumrec(a,center+1,right);
        int maxleftbordersum=0,leftbordersum=0;
         int lrmax=max(maxleftsum,maxrightsum);
        for(int i=center;i>=left;i--)
        {
             leftbordersum+=a[i];
             if(leftbordersum>maxleftbordersum)
                maxleftbordersum=leftbordersum;
        }
        int maxrightbordersum=0,rightbordersum=0;
        for(int i=center+1;i<=right;i++)
        {
            rightbordersum+=a[i];
            if(rightbordersum>maxrightbordersum)
                maxrightbordersum=rightbordersum;
    
        }
        return max(lrmax,maxleftbordersum+maxrightbordersum);
    }
    
    int maxsubsum2(const vector <int> &a)
    {
         return maxsumrec(a,0,a.size()-1);
    }
    //算法四
    //联机算法
    int maxsubsum3(const vector<int >&a)
    {
        int MaxSum=0,ThisSum=0;
        for(int j=0;j<a.size();j++)
        {
            ThisSum+=a[j];
            if(ThisSum>MaxSum)
                MaxSum=ThisSum;
            if(ThisSum<0)
             ThisSum=0;
        }
        return MaxSum;
    }
    int main()
    {
       int input[10];
       for(int i=0;i<5;i++)
       {
           cin>>input[i];
       }
       //注意这里是去给vector容器初始化赋值的时候，区间是[begin,end];
       vector<int>inputVetor(&input[0],&input[4]);
       cout<<maxsubsum(inputVetor)<<endl;
       cout<<maxsubsum1(inputVetor)<<endl;
       cout<<maxsubsum2(inputVetor)<<endl;
       cout<<maxsubsum3(inputVetor)<<endl;
       return 0;
    }