最大子阵列递归

Question

"最大子阵列"问题：

给定一个整数数组nums，找到连续的子数组(包含至少一个数字(，并返回其和。

示例：

输入：nums=[-2,1，-3,4，-1,2,1，-5,4]

输出：6

这应该是一个简单的问题，但由于某种原因，当输入一个大数组时，我的代码会无休止地运行。我希望有人能帮忙：

这是我的代码：

def maxSubCaller(nums):
return maxSub(nums, 0, len(nums)-1)

def maxSub(nums, i, j):
if i == j:
return nums[i]

if j < i or i > j:
return min(nums)

sum_res = sum(nums[i:j + 1])
left_sub = maxSub(nums, i, j-1)
right_sub = maxSub(nums, i+1, j)
return max(sum_res, left_sub, right_sub)

Answer 1

这可能是因为您的实现实际上非常复杂。对于每个递归步骤，都要在两个索引之间求和。sum函数需要循环通过传递的参数，因此最坏情况下的时间复杂度与n^2成比例，其中n是输入列表的长度。

这个问题可以在与输入列表长度成比例的线性时间内解决，如下所示：

def max_sub_arr(nums):
max_sum = nums[0]
local_sum = nums[0]
for i in range(1, len(nums)):
if (nums[i] > local_sum + nums[i]):
local_sum = nums[i]
else:
local_sum += nums[i]
max_sum = max(local_sum, max_sum)
return max_sum
if __name__ == "__main__":
print(max_sub_arr([-2,1,-3,4,-1,2,1,-5,4]))

这与您的算法不同，只在数组中循环一次(不使用sum函数(，执行速度应该更快。

该代码可能有进一步的优化，并且没有错误处理(即nums为空时(。然而，以上内容应该足够快，可以完成您的问题。