IT教程: 连续子数组最大和问题

本邮件内容由第三方提供，如果您不想继续收到该邮件，可点此退订。

连续子数组最大和问题 - lifehack 阅读原文»

问题描述

输入一个整形数组，求数组中连续的子数组使其和最大。比如，数组x

应该返回 x[2..6]的和187.

问题解决

我们很自然地能想到穷举的办法，穷举所有的子数组的之和，找出最大值。

穷举法

i, j的for循环表示x，k的for循环用来计算x之和。

maxsofar = 0
for i = [0, n)
    for j = [i, n)
        sum = 0
        for k = [i, j]
            sum += x[k]
        /* sum is sum of x */
        maxsofar = max(maxsofar, sum)

有三层循环，穷举法的时间复杂度为$O(n^3)$

对穷举法的改进1
我们注意到`x之和 = x之和 + x[j]`，因此在j的for循环中，可直接求出sum。
`maxsofar = 0 for i = [0, n) sum = 0 for j = [i, n) sum += x[j] /* sum is sum of x */ maxsofar = max(maxsofar, sum)`
显然，改进之后的时间复杂度变为$O(n^2)$。

对穷举法的改进2
在计算fibonacci数时，应该还有印象：用一个累加数组（cumulative array）记录前面n-1次之和，计算当前时只需加上n即可。同样地，我们用累加数组cumarr记录：`cumarr = x[0] + . . . +x`，那么`x 之和 = cumarr[j] -cumarr`。
`cumarr[-1] = 0 for i = [0, n) cumarr[i] = cumarr + x maxsofar = 0 for i = [0, n) for j = [i, n) sum = cumarr[j] - cumarr /* sum is sum of x / maxsofar = max(maxsofar, sum)`
时间复杂度依然为$O(n^2)$。
分治法
所谓分治法，是指将一个问题分解为两个子问题，然后分而解决之。具体步骤如下：
先将数组分为两个等长的子数组a, b；
分别求出两个数组a，b的连续子数组之和；
还有一种情况比较容易忽略：有可能最大和的子数组跨越两个数组；
最后比较$m_a$, $m_b$, $m_c$，取最大即可。
在计算$m_c$时，注意：$m_c$必定包含总区间的中间元素，因此求$m_c$等价于`从中间元素开始往左累加的最大值 + 从中间元素开始往右累加的最大值`。
`float maxsum3(l, u) if (l > u) / zero elements / return 0 if (l == u) / one element / return max(0, x[l]) m = (l + u) / 2 / find max crossing to left / lmax = sum = 0 for (i = m; i >= l; i--) sum += x lmax = max(lmax, sum) / find max crossing to right / rmax = sum = 0 for i = (m, u] sum += x rmax = max(rmax, sum) return max(lmax+rmax, maxsum3(l, m), maxsum3(m+1, u));`
容易证明，时间复杂度为$O(nlog \ n)$。

Kadane算法
Kadane算法又被称为扫描法，该算法用到了一个启发式规则：如果前面一段连续子数组的和小于0，那么就丢弃它。其实也蛮好理解的，举个简单例子，比如：数组`-1, 2, 3`，-1为负数，为了使得子数组之和最大，显然不应当把-1计入进内。
max_ending_here记录前面一段连续子数组之和。
`Initialize: max_so_far = 0 max_ending_here = 0 Loop for each element of the array (a) max_ending_here = max_ending_here + x (b) if(max_ending_here < 0) max_ending_here = 0 (c) if(max_so_far < max_ending_here) max_so_far = max_ending_here return max_so_far`
只遍历了一遍数组，因此时间复杂度为$O(n)$。
参考资料
[1] Jon Bentley, Programming Pearls.
[2] GeeksforGeeks, Largest Sum Contiguous Subarray.

本文链接：连续子数组最大和问题，转载请注明。

curl_redir_exec()函数 - 小伢子 阅读原文»

本文链接：curl_redir_exec()函数，转载请注明。

阅读更多内容

IT教程

2014年9月13日星期六

连续子数组最大和问题 - lifehack

对穷举法的改进1
我们注意到`x之和 = x之和 + x[j]`，因此在j的for循环中，可直接求出sum。
`maxsofar = 0 for i = [0, n) sum = 0 for j = [i, n) sum += x[j] /* sum is sum of x */ maxsofar = max(maxsofar, sum)`
显然，改进之后的时间复杂度变为$O(n^2)$。

没有评论:

发表评论

2014年9月13日星期六

连续子数组最大和问题 - lifehack

对穷举法的改进1我们注意到x之和 = x之和 + x[j]，因此在j的for循环中，可直接求出sum。maxsofar = 0for i = [0, n) sum = 0 for j = [i, n) sum += x[j] /* sum is sum of x */ maxsofar = max(maxsofar, sum)显然，改进之后的时间复杂度变为$O(n^2)$。

没有评论:

发表评论

对穷举法的改进1
我们注意到`x之和 = x之和 + x[j]`，因此在j的for循环中，可直接求出sum。
`maxsofar = 0 for i = [0, n) sum = 0 for j = [i, n) sum += x[j] /* sum is sum of x */ maxsofar = max(maxsofar, sum)`
显然，改进之后的时间复杂度变为$O(n^2)$。