Yufan's Blog - Algo 最大连续数列和

最大连续子序列和问题是个很老的面试题了，最佳的解法是 O(n) 复杂度，当然其中的一些小的地方还是有些值得注意的地方的。这里还是总结两种常见的解法，重点关注最后一种 O(n) 的解法即可。

Problem Description

问题是这样的：一个整数数组中的元素有正有负，在该数组中找出一个连续子数组，要求该连续子数组中各元素的和最大，这个连续子数组便被称作最大连续子数组。比如数组 [2, 4, -7, 5, 2, -1, 2, -4, 3] 的最大连续子数组为 [5, 2, -1, 2]，最大连续子数组的和为 5 + 2 - 1 + 2 = 8 。

Divide and Conquer - O(nlogn) Solution

考虑将数组从中间分为两个子数组，则最大子数组必然出现在以下三种情况之一：

• 1、完全位于左边的数组中。
• 2、完全位于右边的数组中。
• 3、跨越中点，包含左右数组中靠近中点的部分。

递归将左右子数组再分别分成两个数组，直到子数组中只含有一个元素，退出每层递归前，返回上面三种情况中的最大值。实现代码如下：

""" Find maximum continuous sum in an array O(nlogn)

T(n) = 2 * T(n/2) + O(n)

Divide and conquer

Idea in general:
max_continuous_sum = max(
    1. max_continuous_sum_in_the_left,
    2. max_continuous_sum_in_the_right,
    3. max_continuous_sum_cross_middle
)
"""


def max_continuous_sum(nums):
    if len(nums) == 0:
        return 0
    if len(nums) == 1:
        return max(0, nums[0])
    left, right = 0, len(nums) - 1
    middle = int((left+right+1)/2)
    return max(
        max_continuous_sum(nums[:middle]),
        max_continuous_sum(nums[middle+1:]),
        max_continuous_sum_cross_middle(nums, left, middle, right)
    )


def max_continuous_sum_cross_middle(nums, left, middle, right):
    left_ward_sum, left_ward_max_sum = 0, 0
    right_ward_sum, right_ward_max_sum = 0, 0
    for i in range(middle, left-1, -1):
        left_ward_sum += nums[i]
        left_ward_max_sum = max(left_ward_max_sum, left_ward_sum)
    for i in range(middle, right+1):
        right_ward_sum += nums[i]
        right_ward_max_sum = max(right_ward_max_sum, right_ward_sum)
    return max(left_ward_max_sum, right_ward_max_sum,
               left_ward_max_sum + right_ward_max_sum - max(nums[middle], 0))

Kadane’s Algorithm - O(n) Solution

Kadane 算法的简单概念是查找数组的所有正连续段（max_ending_here）。并跟踪所有正片段中的最大和连续片段（max_so_far）。每次我们得到一个正数和它与 max_so_far 比较，如果它大于 max_so_far 的话，就更新 max_so_far。

""" Find maximum continuous sum in an array
Algorithm
# init
max_so_far = 0
max_ending_here = -999999999999
for num in nums:
    max_ending_here = max(max_ending_here + num, 0)
    max_so_far = max(max_so_far, max_ending_here)
------------------------------------------------------------
array           | 1 | -2 | 3 | 5 | -3 | 1 |  5 | -3 |  7
------------------------------------------------------------
max_ending_here | 1 |  0 | 3 | 8 |  5 | 6 | 11 |  8 | 15
------------------------------------------------------------
max_so_far      | 1 |  1 | 3 | 8 |  8 | 8 | 11 | 11 | 15
------------------------------------------------------------
"""


def maximum_continuous_sum(nums):
    # init
    max_so_far = 0
    max_ending_here = 0
    # iter
    for num in nums:
        max_ending_here = max(max_ending_here + num, 0)
        max_so_far = max(max_so_far, max_ending_here)
    return max_so_far


if __name__ == '__main__':
    test = [1, -2, 3, 5, -3, 1, 5, -3, 7]
    print(maximum_continuous_sum(test))

Reference

源码传送门。