Sui Xin's Blog

[剑指Offer]连续子数组的最大和

Posted on In Disqus:

题目描述

HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

解题思路

  1. 方法一：不考虑复杂度。直接遍历整个数组，找出每个以当前数开头的子数组的连续数组和，取最大。时间复杂度为$O(n^2)$；
  2. 方法二：找出数组的规律。从头到尾累加数组的数，如果当前的和为非正数，那么加上当前数肯定会变小，所以把当前和抛弃掉重置为当前数，否则当前和更新为加上当前数。设置一个最大和变量，每次判断是否需要更新；
  3. 方法三：动态规划。和方法二思路一样，只不过方式换了一下。函数$f(i)$表示以$i$结尾的子数组的最大连续和，则有公式：

代码

Python(2.7.3)

方法一：$O(n^2)$解法

1
2
3
4
5
6
7
8
9
10
11
12
# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        res = array[0]
        for i in range(len(array)):
            pre = 0
            for j in range(i, len(array)):
                pre += array[j]
                if pre > res:
                    res = pre
        return res

运行时间：22ms
占用内存：5744k

方法二：数组规律

1
2
3
4
5
6
7
8
9
10
11
12
13
# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        max_sum, cur_sum = -0xffffffff, 0
        for i in array:
            if cur_sum <= 0:
                cur_sum = i
            else:
                cur_sum += i
            if cur_sum > max_sum:
                max_sum = cur_sum
        return max_sum

运行时间：25ms
占用内存：5840k

方法三：动态规划

1
2
3
4
5
6
7
8
# -*- coding:utf-8 -*-
class Solution:
    def FindGreatestSumOfSubArray(self, array):
        # write code here
        dp = [i for i in array]
        for i in range(1, len(array)):
            dp[i] = max(array[i], dp[i - 1] + array[i])
        return max(dp)

运行时间：23ms
占用内存：5624k

Related Posts