连续数列

1.题目描述

给定一个整数数组，找出总和最大的连续数列，并返回总和。

示例：

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

2.题目分析

好的，我们使用分治法来解决最大子数组和问题（Maximum Subarray Problem）。

分治法思路

分治法的核心思想是：
将数组分成左右两半，最大子数组和要么在左半部分，要么在右半部分，要么跨越中间。

1. 基本情况：如果数组只有一个元素，直接返回该元素（如果它是负数，最大子数组和也可能是它）。
2. 分解：
   • 计算中间位置 mid。
   • 递归求左半部分的最大子数组和 left_max。
   • 递归求右半部分的最大子数组和 right_max。
3. 跨越中间的最大子数组和：
   • 从中间向左扩展，求包含中间元素的最大和 left_cross_sum。
   • 从中间向右扩展，求包含中间元素的最大和 right_cross_sum。
   • 跨越中间的和 = left_cross_sum + right_cross_sum - nums[mid]（因为中间元素被加了两次，要减去一次）。
4. 合并：返回 max(left_max, right_max, cross_max)。

---

时间复杂度

• 每次递归分成两半，并且每次合并需要 O(n) 时间（计算跨越中间的和）。
• 递归式：T(n) = 2T(n/2) + O(n)
• 由主定理得：O(n log n)

---

代码实现

def maxSubArray(nums):
    def divide_and_conquer(l, r):
        # 基本情况
        if l == r:
            return nums[l]
        
        mid = (l + r) // 2
        
        # 递归求左右部分的最大子数组和
        left_max = divide_and_conquer(l, mid)
        right_max = divide_and_conquer(mid + 1, r)
        
        # 计算跨越中间的最大子数组和
        # 向左扩展
        left_cross_sum = float('-inf')
        curr_sum = 0
        for i in range(mid, l - 1, -1):
            curr_sum += nums[i]
            left_cross_sum = max(left_cross_sum, curr_sum)
        
        # 向右扩展
        right_cross_sum = float('-inf')
        curr_sum = 0
        for i in range(mid + 1, r + 1):
            curr_sum += nums[i]
            right_cross_sum = max(right_cross_sum, curr_sum)
        
        cross_max = left_cross_sum + right_cross_sum
        
        return max(left_max, right_max, cross_max)
    
    return divide_and_conquer(0, len(nums) - 1)

# 示例
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(maxSubArray(nums))  # 输出 6

---

解释示例

输入：[-2, 1, -3, 4, -1, 2, 1, -5, 4]
最大子数组是 [4, -1, 2, 1]，和为 6。
代码通过分治法递归计算，最终返回 6。

---

def maxSub(nums, left: int, right: int):
    maxLeftBorderSum = maxRightBorderSum = float('-inf')
    leftMaxSum = rightMaxSum = float('-inf')
    leftBorderSum = rightBorderSum = 0

    mid = left + (right - left) // 2
    if left == right:
        return nums[left]
    leftMaxSum = maxSub(nums, left, mid)
    rightMaxSum = maxSub(nums, mid + 1, right)

    for i in range(mid, left - 1, -1):
        leftBorderSum += nums[i]
        if leftBorderSum > maxLeftBorderSum:
            maxLeftBorderSum = leftBorderSum

    for i in range(mid + 1, right + 1, 1):
        rightBorderSum += nums[i]
        if rightBorderSum > maxRightBorderSum:
            maxRightBorderSum = rightBorderSum
    #return max(leftMaxSum, rightMaxSum, maxLeftBorderSum + maxRightBorderSum)
    return max(leftMaxSum, rightMaxSum, maxLeftBorderSum+maxRightBorderSum)

if __name__ == "__main__":
    nums = [-2,1,-3,4,-1,2,1,-5,4]
    print(maxSub(nums,0,len(nums)-1))