<求最大子序列>告诉你如何将复杂度从O(n^3)杀到O(n)

发表于 算法 2017-02-27 阅读数: 173

最近在LEETCODE上刚好做到这一道题(53.Maximum Subarray)。突然想到《数据结构》中也有这道题目的例子,于是起兴来个总结。

题目: 给你一个数组,让你求出其中最大的子序列之和。如:输入[-2,1,-3,4,-1,2,1,-5,4],其最大的子序列之和为6([4,-1,2,1]).

PS:还记得时间复杂度怎么计算的吗?

以最坏的情况为基准,数量级至上。嵌套相乘,同级相加。

可能需要说明的函数/定义:

max(a,b) : 返回a,b中较大的那一个。

vector&nums : 传入一个vector库,若你对它很陌生,可以暂时把它看做数组(当然它和数组有区别)。

以下所有代码均只有函数部分。完整代码可在: https://github.com/Ckend/GongZhongHao/tree/master/2.27 中查看。

O(n^3)

首先,最直接的思维是将每一个子序列的和都求出来。temp的作用是:1.求每个子序列的和,2.每次求完都会和result对比,如果比result大,则将值赋给result。每次这两个操作结束,temp都会清零。

int MaxSubSequenceSum(std::vector<int>&nums){

    int temp = 0 , result = 0;

    for (int i = 0 ; i < nums.size(); ++i) {

        for (int j = i; j < nums.size(); ++j) {

            temp = 0;

            for (int k = i; k <= j; ++k) {

                temp += nums[k];

                result = std::max(result, temp);

            }

        }

    }

    return result;

}

这个算法是绝对正确的。但是效率非常低下。演示如下:演示并未展现出全部的可能(或许也有点不太准确,最后黄色部分不应该和紫色部分共同前进),但是就如同紫色部分,所有的子序列都会被检测一遍。

我们会思考是否没必要使用三个循环,也许两个循环就够了?我们从上图看到,其实FOR2和FOR3都可以进行这种筛选最大子序列的操作,因为他们的行进轨迹其实都是一样的。于是或许可以删掉那一个多余的循环。

最大子序列

O(n^2)

int MaxSubSequenceSum(std::vector<int>&nums){

    int temp = 0, result = 0;

    for (int i = 0; i < nums.size(); ++i) {

        for (int j = i; j < nums.size(); ++j) {

            temp += nums[j];

            result = std::max(result, temp);

        }

        temp = 0;

    }

    return result;

}

最大子序列

虽然说O(n^2)是一个比较可以接受的复杂度。但是如果我们想要更加优化的算法。可能就要往抽象领域里延伸了。

这个O(n)的算法仅仅七行代码,但是想要理解清楚可没那么简单。我们可以从中看出,它与O(n^2)算法的最大区别在于,少了一个循环,并且temp = 0 被 temp = std::max(0, temp) 代替。

为什么我们在O(n^2)的算法中需要两次循环?因为我们需要把temp清零以保存下一轮的最大值。但是如果我们舍弃这一步操作呢?当序列中全是正数的时候,毋庸置疑,最大子序列就是它自身,于是我们只需要讨论两种情况:

1.序列中有一个以上的正数

当序列中只有一个正数的时候,自然,子序列就是那一个正数。

当序列有大于两个正数的时候,我们可以确定,最大子序列一定大于0。所以当temp的合小于零的时候,我们可以确定这条序列绝对不是最大子序列,于是将它清零,否则temp不清零。直到遇到真正的最大子序列。

2.序列中全是负数

如果序列中全是负数,那么最大子序列肯定只有一个数。利用result = std::max(result, temp);可以直接判断出来。

O(n)

int MaxSubSequenceSum(std::vector<int>&nums){

    int temp = 0, result = nums[0];

    for (int i = 0; i < nums.size(); ++i) {

        temp += nums[i];

        result = std::max(result, temp);

        temp = std::max(0, temp);

    }

    return result;

}

于是通过这种巧妙的方法,我们成功实现了将算法复杂度优化到O(n)的目标。如果你还是不太明白,我的经验是要不断地归纳总结,总是会有一点收获的。

欢迎关注微信公众号:幻象客www.huanxiangke.com

幻象客 二维码

Add comment