给定一个整数数组 nums,下面代码找到一个具有最大和的连续子数组,并返回其最大和。则下面说法错误的是( )。
import math
def crossSum(nums, left, mid, right):
leftSum = -math.inf
sum_val = 0
for i in range(mid, left - 1, -1):
sum_val += nums[i]
leftSum = max(leftSum, sum_val)
rightSum = -math.inf
sum_val = 0
for i in range(mid + 1, right + 1):
sum_val += nums[i]
rightSum = max(rightSum, sum_val)
return leftSum + rightSum
def helper(nums, left, right):
if left == right:
return nums[left]
mid = left + (right - left) // 2
leftMax = helper(nums, left, mid)
rightMax = helper(nums, mid + 1, right)
crossMax = crossSum(nums, left, mid, right)
return max(leftMax, rightMax, crossMax)
def maxSubArray(nums):
return helper(nums, 0, len(nums) - 1)
上述代码采用分治算法实现
本题算法采用贪心算法
时间复杂度:O(n log n)
由于采用递归方式实现,空间复杂度:O(log n)