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

迈不过友情╰ 2023-06-04 05:58 13阅读 0赞

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

转载于:https://www.cnblogs.com/qwj-sysu/p/4033360.html