最大子列和问题（Maximum Subarray Sum Problem）是经典的动态规划问题之一，目标是在给定的整数数组中找到具有最大和的连续子数组。解决这个问题的经典算法是 **Kadane's Algorithm**，它通过线性时间复杂度 $O(n)$ 来求解。 ### 问题描述 给定一个整数数组 `nums`，找到其中一个具有最大和的连续子数组（子数组至少包含一个元素），返回该最大和。 例如： ```python 输入: [-2,1,-3,4,-1,2,1,-5,4] 输出: 6 解释: 连续子数组 [4,-1,2,1] 的和最大为 6。 ``` ### Python 实现 以下是一个基于 Kadane's Algorithm 的实现[^1]： ```python def max_subarray_sum(nums): max_current = max_global = nums[0] for i in range(1, len(nums)): max_current = max(nums[i], max_current + nums[i]) max_global = max(max_global, max_current) return max_global ``` 在上述代码中： - `max_current` 表示当前子数组的最大和。 - `max_global` 跟踪全局最大值。 #### 示例运行 ```python nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] print(max_subarray_sum(nums)) # 输出: 6 nums = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7] print(max_subarray_sum(nums)) # 输出: 43 ``` ### 变体：记录子数组的起始与结束索引 除了计算最大和之外，有时还需要知道具体的子数组位置。可以通过修改 Kadane's Algorithm 来跟踪起始和结束索引[^1]： ```python def find_max_subarray(nums): max_sum = current_sum = nums[0] start = end = temp_start = 0 for i in range(1, len(nums)): if current_sum < 0: current_sum = nums[i] temp_start = i else: current_sum += nums[i] if current_sum > max_sum: max_sum = current_sum start = temp_start end = i return (start, end, max_sum) ``` #### 示例运行 ```python nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4] print(find_max_subarray(nums)) # 输出: (3, 6, 6) nums = [13, -3, -25, 20, -3, -16, -23, 18, 20, -7, 12, -5, -22, 15, -4, 7] print(find_max_subarray(nums)) # 输出: (7, 10, 43) ``` ### 复杂度分析 - **时间复杂度**: $O(n)$ —— 每个元素仅遍历一次。 - **空间复杂度**: $O(1)$ —— 使用常量级别的额外空间。 ### 应用场景 最大子列和问题广泛应用于信号处理、金融数据分析、图像处理等领域。例如，在股票交易中寻找最佳买入和卖出时机以获取最大收益时，可以将价格变化视为数组，并使用此算法找出最大收益区间。 ---