作者介绍：10年大厂数据\经营分析经验，现任大厂数据部门负责人。
会一些的技术：数据分析、算法、SQL、大数据相关、python
欢迎加入社区：码上找工作
作者专栏每日更新：
题目描述
给定一个整数数组 nums，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
输入格式
- nums：一个整数数组。
输出格式
- 返回整数，表示最大子数组的和。
示例
示例 1
输入: nums = [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。
示例 2
输入: nums = [1] 输出: 1
方法一：动态规划
解题步骤
- 定义状态：
dp[i]表示以nums[i]结尾的最大子数组和。 - 状态转移：
dp[i] = max(nums[i], dp[i-1] + nums[i])，意味着当前元素单独成数组或加入前面的数组。 - 初始化：
dp[0] = nums[0]，只有一个元素时最大和即为该元素。 - 遍历数组：根据状态转移方程更新
dp数组。 - 得到结果：返回
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
算法分析
- 时间复杂度：(O(n))，其中
n是数组nums的长度，我们只需要遍历一次数组。 - 空间复杂度：(O(1))，使用了常数空间存储
dp状态和结果。
方法二：分治法
解题步骤
- 分治思想：将数组分成左右两部分，分别求左右部分的最大子数组和，以及跨越中点的最大子数组和。
- 递归求解：递归地对左右两部分数组应用分治法，直到数组长度为1。
- 合并结果：最大子数组和可能在左侧、右侧或跨越中心，取这三者的最大值。
完整的规范代码
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
算法分析
- 时间复杂度：(O(n \log n))，递归的每层需要 (O(n)) 的时间合并结果，共有 (\log n) 层。
- 空间复杂度：(O(\log n))，递归栈的深度。
方法三：贪心算法
解题步骤
- 初始化变量：设置两个变量，
current_sum表示当前遍历到的子数组的和，max_sum用来存储遍历过程中遇到的最大子数组和。 - 遍历数组：对数组中的每个元素进行遍历，根据贪心策略更新
current_sum和max_sum。 - 更新当前和：如果
current_sum小于0，就重新设置current_sum为当前元素，否则就累加当前元素。 - 更新最大和：每步都取
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
算法分析
- 时间复杂度：(O(n))，其中
n是数组nums的长度，因为我们只需遍历一次数组。 - 空间复杂度：(O(1))，使用了常数额外空间。
方法四：改进的动态规划（空间优化）
解题步骤
- 初始化变量：与标准动态规划方法相似，但只用一个变量来存储上一个状态的
dp值，从而减少空间使用。 - 遍历更新：遍历数组，根据
dp[i-1]更新dp[i]。 - 记录最大和：在遍历过程中持续更新最大子数组和。
完整的规范代码
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
算法分析
- 时间复杂度：(O(n))，只需遍历数组一次。
- 空间复杂度：(O(1))，不使用额外的空间除了几个必要变量。
方法五：分块累计法
解题步骤
- 分块累计：采用分块的方式累计子数组和，每当累计和小于0时重新开始计算。
- 遍历数组：在遍历过程中，对每个分块的和进行计算，并更新全局最大和。
完整的规范代码
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
算法分析
- 时间复杂度：(O(n))，遍历一次数组。
- 空间复杂度：(O(1))，仅使用固定空间。
不同算法的优劣势对比
| 特征 | 方法一: 动态规划 | 方法二: 贪心算法 | 方法三: 分治法 | 方法四: 改进动态规划 | 方法五: 分块累计法 |
| 时间复杂度 | (O(n)) | (O(n)) | (O(n log n)) | (O(n)) | (O(n)) |
| 空间复杂度 | (O(1)) | (O(1)) | (O(log n)) | (O(1)) | (O(1)) |
| 优势 | - 基本且直观 | - 实现简单 | - 适合并行处理 | - 空间高效 | - 直观易懂 |
| 劣势 | - 无显著劣势 | - 需要理解逻辑 | - 较慢 | - 与方法一类似 | - 与贪心相似 |
应用示例
金融分析：
在金螌数据分析中，最大子数组和可以用来确定股票的最优买卖时期，即找出股价变动中的最大盈利窗口。
信号处理：
在处理信号时，寻找最大子数组和可以用来检测一段时间内的最大信号强度，有助于从噪声中提取有用信号。
欢迎关注微信公众号 数据分析螺丝钉
