在Python中，对于一个数字列表，如何找到具有最大和的数字的连续子集范围？

输入的一个示例可能是

nums1 = [-1,4,-3,5,-5]
nums2 = [-1,4]

我想知道这里什么可能是有效的解决方案。谢谢。

def max_subarray_sum_range(nums):
  """
  找到数字列表中具有最大和的连续子集范围。

  Args:
    nums: 数字列表。

  Returns:
    一个包含最大和子集起始索引和结束索引的元组，如果列表为空，则返回 (None, None)。
  """
  if not nums:
    return (None, None)

  max_so_far = nums[0]
  current_max = nums[0]
  start_index = 0
  end_index = 0
  max_start_index = 0

  for i in range(1, len(nums)):
    if current_max + nums[i] < nums[i]:
      current_max = nums[i]
      start_index = i
    else:
      current_max += nums[i]

    if current_max > max_so_far:
      max_so_far = current_max
      max_start_index = start_index
      end_index = i

  return (max_start_index, end_index)

# 测试用例
nums1 = [-1, 4, -3, 5, -5]
nums2 = [-1, 4]

start_index1, end_index1 = max_subarray_sum_range(nums1)
start_index2, end_index2 = max_subarray_sum_range(nums2)

print(f"nums1 的最大和子集范围：({start_index1}, {end_index1})") 
print(f"nums2 的最大和子集范围：({start_index2}, {end_index2})") 

此代码使用 Kadane 算法在 O(n) 时间复杂度内找到具有最大和的连续子数组。以下是工作原理的逐步说明：

1. 初始化：
2. 将 max_so_far 和 current_max 初始化为列表中的第一个元素。这表示到目前为止遇到的最大和以及以当前元素结束的子数组的最大和。

3. 将 start_index 、 end_index 和 max_start_index 初始化为 0。这些变量分别跟踪当前子数组的起始索引、结束索引和具有最大和的子数组的起始索引。

4. 迭代列表：

5. 从列表中的第二个元素循环到最后一个元素。

6. 对于每个元素，我们计算：

   • 包含当前元素的子数组的最大和 ( current_max + nums[i] )。
   • 以当前元素作为新子数组的起始元素的最大和 ( nums[i] )。
   • 如果以当前元素作为新子数组的起始元素的最大和更大，我们将 current_max 更新为新和，并将 start_index 更新为当前索引。
   • 否则，我们继续将当前元素添加到当前子数组中，并将 current_max 更新为包含当前元素的子数组的最大和。

7. 更新 max_so_far ：

8. 对于每次迭代，如果 current_max 大于 max_so_far ，我们将 max_so_far 更新为 current_max 、将 max_start_index 更新为 start_index ，并将 end_index 更新为当前索引。这确保我们跟踪迄今为止遇到的最大和及其相应的起始和结束索引。

9. 返回结果：

10. 循环完成后，我们返回一个包含 max_start_index 和 end_index 的元组，它们表示具有最大和的子数组的起始和结束索引。

此算法有效地遍历列表一次，在每次迭代中跟踪最大和及其索引，从而使其成为解决此问题的有效方法。