LeetCode第53题：最大子数组和【python 5种算法】

作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
LeetCode解锁1000题: 打怪升级之旅
python数据分析可视化：企业实战案例

题目描述

给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

输入格式

• nums：一个整数数组。

输出格式

• 返回整数，表示最大子数组的和。

示例

示例 1

输入: nums = [-2,1,-3,4,-1,2,1,-5,4]
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
1
2
3

示例 2

输入: nums = [1]
输出: 1
1
2

方法一：动态规划

解题步骤

1. 定义状态：dp[i] 表示以 nums[i] 结尾的最大子数组和。
2. 状态转移：dp[i] = max(nums[i], dp[i-1] + nums[i])，意味着当前元素单独成数组或加入前面的数组。
3. 初始化：dp[0] = nums[0]，只有一个元素时最大和即为该元素。
4. 遍历数组：根据状态转移方程更新 dp 数组。
5. 得到结果：返回 dp 数组中的最大值，即为所求。

完整的规范代码

def maxSubArray(nums):
    """
    动态规划解法求最大子数组和
    :param nums: List[int], 输入的整数数组
    :return: int, 最大子数组的和
    """
    if not nums:
        return 0
    
    n = len(nums)
    dp = nums[0]
    max_sum = dp
    for i in range(1, n):
        dp = max(nums[i], dp + nums[i])
        if dp > max_sum:
            max_sum = dp
    return max_sum

# 示例调用
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))  # 输出: 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

算法分析

• 时间复杂度：(O(n))，其中 n 是数组 nums 的长度，我们只需要遍历一次数组。
• 空间复杂度：(O(1))，使用了常数空间存储 dp 状态和结果。

方法二：分治法

解题步骤

1. 分治思想：将数组分成左右两部分，分别求左右部分的最大子数组和，以及跨越中点的最大子数组和。
2. 递归求解：递归地对左右两部分数组应用分治法，直到数组长度为1。
3. 合并结果：最大子数组和可能在左侧、右侧或跨越中心，取这三者的最大值。

完整的规范代码

def maxSubArray(nums):
    """
    分治法解决最大子数组和问题
    :param nums: List[int], 输入的整数数组
    :return: int, 最大子数组的和
    """
    def maxSubArrayDivideAndConquer(l, r):
        if l == r:
            return nums[l]
        mid = (l + r) // 2
        left_max = maxSubArrayDivideAndConquer(l, mid)
        right_max = maxSubArrayDivideAndConquer(mid + 1, r)
        
        max_left_border_sum = nums[mid]
        max_right_border_sum = nums[mid + 1]
        tmp = 0
        for i in range(mid, l - 1, -1):
            tmp += nums[i]
            if tmp > max_left_border_sum:
                max_left_border_sum = tmp
        
        tmp = 0
        for i in range(mid + 1, r + 1):
            tmp += nums[i]
            if tmp > max_right_border_sum:
                max_right_border_sum = tmp
        
        return max(left_max, right_max, max_left_border_sum + max_right_border_sum)
    
    return maxSubArrayDivideAndConquer(0, len(nums) - 1)

# 示例调用
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))  # 输出: 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

算法分析

• 时间复杂度：(O(n \log n))，递归的每层需要 (O(n)) 的时间合并结果，共有 (\log n) 层。
• 空间复杂度：(O(\log n))，递归栈的深度。

方法三：贪心算法

解题步骤

1. 初始化变量：设置两个变量，current_sum 表示当前遍历到的子数组的和，max_sum 用来存储遍历过程中遇到的最大子数组和。
2. 遍历数组：对数组中的每个元素进行遍历，根据贪心策略更新 current_sum 和 max_sum。
3. 更新当前和：如果 current_sum 小于0，就重新设置 current_sum 为当前元素，否则就累加当前元素。
4. 更新最大和：每步都取 current_sum 和 max_sum 的较大值更新 max_sum。

完整的规范代码

def maxSubArray(nums):
    """
    使用贪心算法计算最大子数组和
    :param nums: List[int], 输入的整数数组
    :return: int, 最大子数组的和
    """
    current_sum = max_sum = nums[0]
    for num in nums[1:]:
        current_sum = max(num, current_sum + num)
        max_sum = max(max_sum, current_sum)
    return max_sum

# 示例调用
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))  # 输出: 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14

算法分析

• 时间复杂度：(O(n))，其中 n 是数组 nums 的长度，因为我们只需遍历一次数组。
• 空间复杂度：(O(1))，使用了常数额外空间。

方法四：改进的动态规划（空间优化）

解题步骤

1. 初始化变量：与标准动态规划方法相似，但只用一个变量来存储上一个状态的 dp 值，从而减少空间使用。
2. 遍历更新：遍历数组，根据 dp[i-1] 更新 dp[i]。
3. 记录最大和：在遍历过程中持续更新最大子数组和。

完整的规范代码

def maxSubArray(nums):
    """
    使用改进的动态规划算法（空间优化版本）求最大子数组和
    :param nums: List[int], 输入的整数数组
    :return: int, 最大子数组的和
    """
    n = len(nums)
    current = max_sum = nums[0]
    for i in range(1, n):
        current = max(nums[i], current + nums[i])
        max_sum = max(max_sum, current)
    return max_sum

# 示例调用
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))  # 输出: 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

算法分析

• 时间复杂度：(O(n))，只需遍历数组一次。
• 空间复杂度：(O(1))，不使用额外的空间除了几个必要变量。

方法五：分块累计法

解题步骤

1. 分块累计：采用分块的方式累计子数组和，每当累计和小于0时重新开始计算。
2. 遍历数组：在遍历过程中，对每个分块的和进行计算，并更新全局最大和。

完整的规范代码

def maxSubArray(nums):
    """
    使用分块累计法求最大子数组和
    :param nums: List[int], 输入的整数数组
    :return: 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

# 示例调用
print(maxSubArray([-2,1,-3,4,-1,2,1,-5,4]))  # 输出: 6
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

算法分析

• 时间复杂度：(O(n))，遍历一次数组。
• 空间复杂度：(O(1))，仅使用固定空间。

不同算法的优劣势对比

应用示例

金融分析：
在金螌数据分析中，最大子数组和可以用来确定股票的最优买卖时期，即找出股价变动中的最大盈利窗口。

信号处理：
在处理信号时，寻找最大子数组和可以用来检测一段时间内的最大信号强度，有助于从噪声中提取有用信号。