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

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

2024-07-27 23:45:49   216人阅读

向量[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. 下界：最好的时间复杂度

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


联系
我们