@LIUHUAN 2016-05-06T21:03:59.000000Z 字数 6559 阅读 1314

Maximum Subarray

algorithm

这个问题我们先看下问题的描述：

问题描述

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

问题来自于Leetcode:Maximum Subarray

问题分析

简单来说，就是在一个数组 $A_{1...n}$ 中找到一个子数组 $A_{i...j}$ 使得
$\sum_{k=i}^j A_k$ 最大，也有找最小值的（可以转化为找最大值的问题，不再详述）

那么最直接的想法，就是对于每一个 $（i,j）,i \le j$ 遍历整个数组，用一个最大值标记一下，就能都找到最大值了。对于每一个 $i,j$ 组合总共有 $\frac{n(n+1)}{2}$ 个子数组，都遍历一次数组，那么可以看出来整个的复杂度为 $O(n^3)$

解决方案

1.按着上面的思路，我们可以写出如下的程序来

int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        int max = 0x80000001;//最小的32位整数
        int sum = 0;
        for(int i =0;i<n;++i){
             for(int j=0;j<n;++j){
                 sum = 0;
                 /*计算 A[i,j] 的和*/
                 for(int k=i;k<=j;++k){
                    sum += nums[k]; 
                 }
                /**更新最大值max*/
                if(sum > max)
                    max = sum;
             }
        }
        return max;
    }

但是这种方法在Leetcode上面没有通过，因为超时了。时间复杂度太高了。如果数据很大，那么会很慢。

2.上面的解决方案1需要重复计算每个子数组的部分过程

上面的算法我们每次是按着 $(i,j)$ 对来计算的，如果我们当纯来想如何求所有的子数组的过程，可以发现，对于一个特定的 $i$ ，我们可以计算 $(i,i),(i,i+1),(i,i+2) \dots (i,n-1)$ 的和，
$\sum_{k=i}^{j+1}A_k = A_{j+1} + \sum_{k=i}^{j}A_k$ 可以充分利用前面计算出来的 $\sum_{k=i}^{j}A_k$ ,来降低时间复杂度。

那么就不用对于每一个 $(i,j)$ 都从 $i$ 到 $j$ 遍历数组，那么时间复杂度可以降低为 $O(n^2)$

所以可以有如下优化的代码

int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        int max = 0x80000001;//最小的32位整数
        int sum = 0;
        for(int i=0;i<n;++i){
            sum = 0;
            /**对于某个特定的i 分别计算A[i,i+1],A[i,i+2],...A[i,n-1]的和*/
            for(int j=i;j<n;++j){
                sum += nums[j];
                /**更新最大值max*/
                if(sum > max )
                    max = sum;
            }
        }
        return max;
}

噩耗再次传来，⊙﹏⊙b汗

没有通过leetcode测试，还是超时了

那么看样子时间复杂度还需要降低才可以。不然找不到工作了。。。

2.下面采用的分治的算法，从最大子数组出现的位置来考虑的。可以参考<算法导论>的第4章内容

分治的思想是，把数组 $A_{i \dots j},i \le j$ 看成两个部分，可以认为是从数组中间分割成
$A_{i \dots k}$ 和 $A_{k+1 \dots j},k = \frac{i+j}{2}$ 两个数组，那么我们的目标就是通过求这两个子数组的最大值，然后求得目前这个数组 $A_{i \dots j}$ 的最大子数组和的值。那么问题来了，如果你知道了 $A_{i \dots k}$ 的最大子数组的和 $max\_left$ 和 $A_{k+1 \dots j}$ 的最大子数组的和 $max\_right$ ,你怎么求解目前这个数组 $A_{i \dots j}$ 的最大子数组的和？⊙﹏⊙b汗

可以分析下，如果知道了 $max\_left$ 和 $max\_right$ ，那么我们分析下 $max\_left$ 和 $max\_right$ 的构成。

$max\_left = \sum_{t=start}^{end}A_t,start \ge i , end \lt k$

$max\_right = \sum_{t=start}^{end}A_t,start \gt k , end \le j$

从上面的表达式可以看出来 $max\_left$ 是 $k$ 左边的某个子数组的和， $max\_right$ 是 $k$ 右边的某个子数组的和，具体是什么我们可以先不用管了，因为，这两个值都是假设已经知道的。

那么整个 $A_{i \dots j}$ 最大子数组的和，出现的子数组的位置还有一种可能，那就是，在左边有一部分，右边也有一部分，并且包含 $A_k$ 这个元素。也就是子数组和的形式为 $\sum_{t=start}^{k-1}A_t + A_k + \sum_{t=k+1}^{end}A_t$ ，哎呦这样看来不就是和之前 $\sum_{t=i}^ {j}A_t$ 形式一致了么？有神马意义⊙﹏⊙b汗

客官，请慢！！我明天再写吧。

那么，我们就先分别递归求的左边和右边的最大子数组和的值，然后考虑下和当前的跨越中点的那个最大子数组和进行比较，获取他们三个当中最大的那一个。

那么如何求的跨越中点的子数组的最大值呢？

跨越中点有一个特点，就是左边是以中点 $k = \frac{i+j}{2}$ 所在元素结尾，右边是以这个元素为开始，那么由第二种解决方案的思路，我们就可以分别从 $k$ 开始，向左边和右边进行遍历找到最大的那个。其实这种遍历是 $O(n)$ 的复杂度的⊙﹏⊙b汗

那么我们就写下来代码看看。

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return nums[0];
    return maxSubArray_help(nums,0,n-1);
}
int maxSubArray_help(vector<int>& nums,int begin,int end){
    if(begin == end)
        return nums[end];
    int mid = (begin + end)>>1;
    /**左边子数组的最大值子数组值*/
    int max_left = maxSubArray_help(nums,begin,mid);
    /**右边子数组的最大值子数组值*/
    int max_right = maxSubArray_help(nums,mid + 1,end);
    /**跨越中点的最大值子数组值*/
    int max_cross = maxCrossMid(nums,begin,mid,end);
    return max(max(max_left,max_right),max_cross);
}
/*maxCrossMid函数的时间复杂度实际为O(n)*/
int maxCrossMid(vector<int>& nums,int begin,int mid ,int end){
    int left_max = 0x80000001;//最小的32位整数
    int right_max = 0x80000001;
    int sum = 0;
    /*计算以mid结尾的最大的子数组和，左边子数组*/
    for(int i = mid ;i>=begin;--i){
        sum += nums[i];
        if(sum > left_max)
            left_max = sum;
    }
    sum = 0;
    /*计算以mid+1开始的最大的子数组和，右边子数组*/
    for(int i=mid+1;i<=end;++i){
        sum += nums[i];
        if(sum > right_max)
            right_max = sum;
    }
    return left_max + right_max;
}

提交到Leetcode，如果还通不过，那么，你觉得我能找到工作么？黔驴技穷了都⊙﹏⊙b汗（还是参考算法导论的内容）

好消息是通过了测试，坏消息是，运行的速度很慢。很慢。。

我们来分析下这个算法慢在哪里,这个算法是一个分治的算法，那么我们按着分治的思想列出时间复杂度的计算表达式 $T(n) = 2T(\frac{n}{2}) + O(n)$ ,为什么最后面一项是 $O(n)$ ,这项就表示我们计算跨越中点的最大子数组和的时间复杂度。 maxCrossMid这个函数的最坏情况下是最大子数组就是从begin开始到end结束的和，那么begin和end最坏的情况就是0到n 所以时间复杂度是 $O(n)$

那么这个表达式的结果是什么呢？

根据主定理，我们可以知道这个解的下界是 $O(nlgn)$ 也就是 $\Theta(nlgn)$ ,当然这个算法比 $O(n^2)$ 要快，不然也通不过测试。。

那么他们怎么运行的那么快呢？有没有线性时间的算法呢？

3.线性时间的算法,思想参考算法导论的第4章的习题

线性算法的思想是基于动态规划，把问题转化为一个较小的子问题。思考是这么想的，但是实际求解的过程还是从子问题逐渐到整个问题的过程。我也不知道我在说神马⊙﹏⊙b汗

对于数组从左到右处理，记录到目前为止，他的意思是到你遍历的某个元素为止的已经处理过的最大子数组的，基于下面的观察，如果已知 $A[i \dots j]$ 的最大子数组，那么可以根据如下的性质将解扩展到为 $A[i \dots j+1]$ 的最大子数组： $A[i \dots j+1]$ 的最大子数组，要么是 $A[i \dots j]$ 的最大子数组，要么是某个子数组 $A[m \dots j+1]，i \le m \le j+1$ 。以 $A_{j+1}$ 结尾的子数组。

那么我们可以想到，如果 $A[i \dots j+1]$ 的最大子数组，和 $A[i \dots j]$ 的最大子数组一样，那很好实现，但是这只是一种情况。其实重点在 $A[i \dots j+1]$ 的子数组是 $A[m \dots j+1]，i \le m \le j+1$ ，如果是这种情况怎么确定 $A[m \dots j+1]$ 呢？也就是求解以 $A_{j+1}$ 结尾的最大子数组，按着解决方案三的思想，我们可以从 $A_{j+1}$ 向左遍历，求解一个最大的子数组，但是这种很明显就提高了复杂度，对于每一个 $j$ 你都要向左遍历，那么时间复杂度就成为 $O(n^2)$ 了⊙﹏⊙b汗

其实我们忘了一个假设，那就是当你处理到 $A_{j+1}$ 的时候，我们已经知道以 $A_{i}$ 结尾的最大子数组，对应于算法导论中提到的记录目前为止处理过的最大子数组。那么假设 $sum_j=\sum_{t=m}^{j}A_t$ 记录以 $A_j$ 结尾的最大子数组，那么可以得到

$sum_{j+1}=\left\{ \begin{array}{rcl} \sum_{t=m}^{j}A_t + A_{j+1} & & {\sum_{t=m}^{j}A_t + A_{j+1} \gt A_{j+1} } \\ A_{j+1} & & {\sum_{t=m}^{j}A_t + A_{j+1} \le A_{j+1} } \end{array} \right.$

这样就把以 $A_{j+1}$ 结尾的最大子数组找出来了，那么到 $A_{j+1}$ 为止的最大子数组（可能不是以 $A_{j+1}$ 结尾），还没有找出来，这就需要我们从开始记录一个到 $A_{j+1}$ 为止的最大子数组，假设为 $max_j$ 表示到 $A_{j}$ 为止的最大子数组，然后和以 $A_{j+1}$ 结尾的最大子数组进行比较，取最大的那个，

$max_{j+1} = \left\{ \begin{array}{rcl} max_{j} & & max_{j} \gt sum_{j+1}\\ sum_{j+1} & & max_{j} \le sum_{j+1} \end{array} \right.$

这样就可以完成求解到 $A_{j+1}$ 为止，最大的子数组。把过程弄明白之后，那就开始写程序。

int maxSubArray(vector<int>& nums) {
    int n = nums.size();
    if(n == 0)
        return 0;
    if(n == 1)
        return nums[0];
    vector<int> Max(n,0x80000001);
    vector<int> sum(n,0);
    sum[0] = nums[0];
    Max[0] = nums[0];
    for(int i=1;i<n;++i){
        /*以nums[i]结尾的最大子数组*/
        sum[i] = max(sum[i-1] + nums[i],nums[i]);
        /*到i为止的最大子数组*/
        Max[i] = max(sum[i],Max[i-1]);
    }
    /*返回到n-1为止的最大子数组，也就是整个数组的最大子数组*/
    return Max[n-1];
}

Leetcode提交通过，速度任然很慢，这是怎么一回事⊙﹏⊙b汗

分析下复杂度，时间复杂度为 $O(n)$ 只扫描一遍数组。

空间复杂度为 $O(2n)$ 因为用到了两个额外的数组Max和sum难道这个是慢的原因（有可能）

那么下面的思路就是对这个进行优化。

4.解决方案三的优化

我们看着方案三的代码，可以看出来，其实我们没有必要把全局的最后求解的最大值和每次以 $A_{j}$ 为止的最大值分开来求，只要存放在一个变量里面就可以了，因为到 $A_{j}$ 为止的最大值只使用了一次就结束了，就在和以 $A_{j}$ 结尾的最大值进行比较，所以可以有下面的优化一步的代码。

  int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        vector<int> sum(n,0);
        sum[0] = nums[0];
        int max_sum = nums[0];
        for(int i=1;i<n;++i){
            /*以nums[i]结尾的最大子数组*/
            sum[i] = max(sum[i-1] + nums[i],nums[i]);
            /*到i为止的最大子数组*/
            max_sum = max(max_sum , sum[i]);
        }
        /*返回到n-1为止的最大子数组，也就是整个数组的最大子数组*/
        return max_sum;
}

5.解决方案四的进一步优化

在上一步的优化当中我们可以看出来，其实以 $A_{j}$ 结尾的最大子数组的值也是在求解以 $A_{j+1}$ 结尾的最大子数组的时候用到一次，其他的时候并不会用到，所以我们可以把这个sum数组也优化了，具体的可以用变量 $sum\_cur$ ，表示以 $A_{i}$ 结尾的最大子数组的和，然后比较 $sum\_cur + A_{j+1}$ 和 $A_{j+1}$ 的大小，取最大的那个就代表到以 $A_{j+1}$ 结尾的最大子数组的和。

这样我们就可以写出来，网上一般会直接给出的动态规划最后的结果。

当然还有其他的写法，可以主要思想就是这样。

int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        if(n == 0)
            return 0;
        if(n == 1)
            return nums[0];
        int sum_cur = nums[0];
        int max_sum = nums[0];
        for(int i=1;i<n;++i){
            /*以nums[i]结尾的最大子数组*/
            if(sum_cur < 0)
                sum_cur = nums[i];
            else 
                sum_cur += nums[i];
            /*到i为止的最大子数组*/
            if(sum_cur > max_sum)
                max_sum = sum_cur;
        }
        /*返回到n-1为止的最大子数组，也就是整个数组的最大子数组*/
        return max_sum;
}

6.总结

对于一个问题首先要想到它最为直接，一般的方法，比如这个题的方案1和方案2，首先想到这些直接的算法，然后观察对这种方法进行改进。

我很不赞成直接给出最后一种优化后的结果的答案，因为这个比较难于理解，至少是对我来说，如果你能直接看懂这个优化后的结果，那么可以用这种思想去做下Leetcode的Maximum Product Subarray这个题的思路和本题类似，后续的内容也会写到这个题。

曾经发生过两行代码来解决这个问题的争论，确实优化之后的核心代码确实只有两行，哈哈。

对于没见过的题，弄懂别人的解法是学习，能够应用之前学习到的方法解决问题是能力

7.参考内容

算法导论第4章

Leetcode:Maximum Subarray