【LeetCode】最大子列和问题（53 Maximum Subarray）

最近在学习一些常用的经典算法，比较经典的一个问题就是给定一个序列，求连续子列的最大和。

用数学语言描述如下：

给定序列

[-2,1,-3,4,-1,2,1,-5,4]

计算出： $$max([0,…, \sum A_k])$$

这个问题使用在线最优化求解(Online Optimization)算法是效率最高的,只需要维护两个变量，一次循环就可以完成。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        max_sum =  nums[0]
        current_sum = 0
        for num in nums:
            current_sum += num
            if current_sum > max_sum:
                max_sum = current_sum
            if current_sum < 0:
                current_sum = 0; # 不可能使后面的和增大，抛弃
                
        return max_sum

下面是运行结果：

可见这是执行效率比较高的解法，时间复杂度为O(n)，但是 LeetCode 还推荐去练习另一种分而治之的解决办法，应该是类似二分法。有时间再去实现下。

Contents