首页 > 代码库 > 算法设计--求连续子向量的最大和问题--论想法思路的重要性

算法设计--求连续子向量的最大和问题--论想法思路的重要性

向量[31,-41,59,26,-53,58,97,-93,-23,84]

算法一:直接求解,简单粗暴,没有什么想法可言,复杂度是O(N3)

    // 方法一,接近O(n3)    int maxsofar1=0;    int count=0;    for (int i = 0; i < 10; ++i)    {        for (int j = 0; j < 10; ++j)        {            int sum=0;            for (int k = i; k < j; ++k)            {                sum+=vec[k];                count++;            }            maxsofar1 = max(maxsofar1,sum);        }    }    cout<<maxsofar1<<" "<<count<<endl;

 算法二:算法一的改进,其实算法一的第二个循环和第三个循环是可以直接合并,于是得到了第一个O(n2)的算法

    int maxsofar2=0;count=0;    for (int i = 0; i < 10; ++i)    {        int sum=0;        for (int j = i; j < 10; ++j)        {            sum+=vec[j];            count++;            maxsofar2=max(maxsofar2,sum);        }    }    cout<<maxsofar2<<" "<<count<<endl;

 

对求sum的方法改变一下,可以得到另外一个版本

    int tem[10]={0};    tem[0]=vec[0];    for(int i=1;i<10;i++) tem[i]=tem[i-1]+vec[i];    maxsofar2=0;    count=0;    for (int i = 0; i < 10; ++i)    {        int sum=0;        for (int j = i; j < 10; ++j)        {            sum=tem[j]-tem[i-1];            count++;            maxsofar2=max(maxsofar2,sum);        }    }    cout<<maxsofar2<<" "<<count<<endl;

 

 算法三,分治算法,时间复杂度是O(nLog(n))

分治原理:要解决规模为n的问题,可以递归的解决两个规模接近n/2的子问题,然后对他们的答案进行合并可以得到整个问题的答案

在这个例子中,每次把向量分为左右两个大小近似相等的子向量a和b

                               a b                                               

分别找出a和b中最大的子向量Ma和Mb

                        Ma                                                                   Mb                                       

那么答案要么在Ma中,要么是Mb中,要么是跨越a和b的边界,为了是递归可以顺利的进行,我们这里的Ma和Mb是从ab的中间分别向两边计算的,

所以如果最大向量在跨越ab的边界的话,那么最大值便是Ma+Mb,要么是Ma或者Mb

int max(int a,int b,int c){return (((a>b)?a:b)>c)?((a>b)?a:b):c;}int a=0;int maxsum3(int l,int u){    if(l>u) return 0;//空向量的时候    if(l==u) return max(0,vec[l]);//向量只有一个元素    int mid=(l+u)/2;    int lmax,sum;lmax=sum=0;    for(int i=mid;i>=l;--i)    {        sum+=vec[i];        lmax=max(lmax,sum);        a++;    }    int rmax;rmax=sum=0;    for(int j=mid+1;j<=u;++j)    {        sum+=vec[j];        a++;        rmax=max(sum,rmax);    }    return max(lmax+rmax,maxsum3(l,mid),maxsum3(mid+1,u));}    cout<<maxsum3(0,9)<<" "<<a<<endl;

算法四:扫描算法,O(n)的时间复杂度就ok了,是线性算法

算法思想:前i个元素中,最大子向量要么在前i-1个元素中,要么其结束位置为i。

这么理解呢?可以这么来理解:

向量[31,-41,59,26,-53,58,97,-93,-23,84]

我们用一个maxsofar4来存储最大的值,用max_ending_here来存储前i个元素中最大的值

以我们这个向量为例,当i=1的时候,maxsofar4=max_ending_here=31,但max_ending_here+vec[1]<0,所以x_ending_here在这里结束了,max_ending_here=0,而maxsofar4不变

当i=2的时候,max_ending_here是用来记录每一次的最大值,当max_ending_here<0 的时候终止,重新记录,而maxsofar4记录的是max_ending_here最大的那个(结果)

    int maxsofar4=0,max_ending_here=0;    for (int i = 0; i < 10; ++i)    {        max_ending_here=max(max_ending_here+vec[i],0);        maxsofar4=max(maxsofar4,max_ending_here);    }    cout<<maxsofar4<<endl;

 

 

纵观这四个算法,最简答的想法代码也是相对是比较长的,最复杂的想法代码却是最短的、效率最高的和运行速度最快的,有时候就是这么神奇,所以说有时候不要急着写代码,idea才是最重要的

 最后总结一下几个重要的算法设计技术:

  1. 保存状态,避免重复计算

  2. 将信息预处理至数据结构中

  3. 分治算法

  4. 扫描算法:如何将x[0...i-1]的解扩展为x[0....i]的解

  5. 累积:跟2有关系

  6. 下界:最好的时间复杂度

算法设计--求连续子向量的最大和问题--论想法思路的重要性