给定一个整数数组nums,下面代码找到一个具有最大和的连续子数组,并返回其最大和。则下面说法错误的是( )。

hd308516 单选题 共 个子题
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)
A

上述代码采用分治算法实现

B

本题算法采用贪心算法

C

时间复杂度: $O(\log n)$

D

由于采用递归方式实现,空间复杂度: $O(\log n)$

正在加载题目数据…
已答 /
子题
该题型需在试卷/作业中作答,单题练习暂不支持
答案解析
讨论
发布
登录后参与讨论 立即登录
发布讨论需先绑定并验证手机号 去绑定手机号
加载中…
我
我
回复 @
回复 @
发送
还没有人讨论,来发表第一条吧