首页
登录 | 注册

连续子数组最大和

1. 问题描述

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

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

2. 问题解决

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

穷举法

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

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

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

对穷举法的改进1

我们注意到x[i..j]之和 = x[i..j-1]之和 + 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[i..j] */
        maxsofar = max(maxsofar, sum)

显然,改进之后的时间复杂度变为\(O(n^2)\)

对穷举法的改进2

在计算fibonacci数时,应该还有印象:用一个累加数组(cumulative array)记录前面n-1次之和,计算当前时只需加上n即可。同样地,我们用累加数组cumarr记录:cumarr[i] = x[0] + . . . +x[i],那么x [i.. j]之和 = cumarr[j] -cumarr[i - 1]

cumarr[-1] = 0
for i = [0, n)
    cumarr[i] = cumarr[i-1] + x[i]
    
maxsofar = 0
for i = [0, n)
    for j = [i, n)
        sum = cumarr[j] - cumarr[i-1]
        /* sum is sum of x[i..j] */
        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[i]
        lmax = max(lmax, sum)
    
    /* find max crossing to right */
    rmax = sum = 0
    for i = (m, u]
        sum += x[i]
        rmax = max(rmax, sum)

    return max(lmax+rmax,
                maxsum3(l, m),
                maxsum3(m+1, u));

容易证明,时间复杂度为\(O(n*log \ n)\)

动态规划

Kadane算法又被称为扫描法,为动态规划(dynamic programming)的一个典型应用。我们用DP来解决最大子数组和问题:对于数组\(a\),用\(c_i\)标记子数组\(a[0..i]\)的最大和,那么则有

\[ c_i = \max \{ a_i, c_{i-1} + a_i \} \]

子数组最大和即为\(\max c_i\)。Kadane算法比上面DP更进一步,不需要用一个数组来记录中间子数组和。通过观察容易得到:若\(c_{i-1} \leq 0\),则\(c_i = a_i\)。用\(e\)表示以当前为结束的子数组的最大和,以替代数组\(c\);那么

\[ e = \max \{ a_i, e + a_i \} \]

Python实现如下:

def max_subarray(A):
    max_ending_here = max_so_far = A[0]
    for x in A[1:]:
        max_ending_here = max(x, max_ending_here + x)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far

max_ending_here对应于标记\(e\)max_so_far记录已扫描到的子数组的最大和。Kadane算法只扫描了一遍数组,因此时间复杂度为\(O(n)\).

3. 参考资料

[1] Jon Bentley, Programming Pearls.
[2] GeeksforGeeks, Largest Sum Contiguous Subarray.


相关文章

  • Windbg分析高内存占用问题
    1. 问题简介 最近产品发布大版本补丁更新,一商超客户升级后,反馈系统经常奔溃,导致超市的收银系统无法正常收银,现场排队付款的顾客更是抱怨声声.为了缓解现场的情况, 客户都是手动回收IIS应用程序池才能解决. 这样的后果是很严重的,接到反馈 ...
  • Detours HOOK 库 Hook 过滤LoadLibraryExW 一丶简介 1.1 Detours库简介 Detours是微软提供的HOOK库.为我们Hook提供了方便.再也不用手撸 HOOK了.当然手撸比较好.可以锻炼.不过工作中 ...
  • LSTM实现中文文本情感分析
    1. 背景介绍 文本情感分析是在文本分析领域的典型任务,实用价值很高.本模型是第一个上手实现的深度学习模型,目的是对深度学习做一个初步的了解,并入门深度学习在文本分析领域的应用.在进行模型的上手实现之前,已学习了吴恩达的机器学习和深度学习的 ...
  • 目录 引入 简单工厂 抽象工厂 Spring的bean工厂 模拟Spring工厂实现 模拟IOC 引入 假设有一个司机, 需要到某个城市, 于是我们给他一辆汽车 public class Demo { public static void ...
  • ERP不规范,同事两行泪
    最近的很多次对外交流,都聊到了ERP建设的话题,并且无一例外的不那么让人省心,回想我这么多年走过的ERP坑坑路,在这里也写下经验和总结,希望能给正在或者即将走上ERP建设路的企业一些思考和帮助. 导读 1.几个瞎眼而普遍的案例 2.ERP的 ...
  • 我是一名项目经理,在过去的四个月里,我把一个项目带崩了(上线后频出问题,用户无法使用).在最近的几天,我每天都在反思自己,我都在问自己以下几个问题: 1.我做错了什么? 2.我在其中占有多重的因素? 以下内容,我将回答以上问题,并在最后说一 ...

2019 cecdns.com webmaster#cecdns.com
12 q. 0.082 s.
京ICP备10005923号