用四种方法求一个序列的最大连续子序列的和
时间: 2024-03-01 08:55:41 浏览: 28
以下是四种常用方法求一个序列的最大连续子序列的和:
1. 蛮力法:对于每一个子序列,计算它们的和,最后找出最大值。时间复杂度为 O(n^2)。
```python
def max_subarray_sum_brute_force(nums):
n = len(nums)
max_sum = float("-inf")
for i in range(n):
cur_sum = 0
for j in range(i, n):
cur_sum += nums[j]
max_sum = max(max_sum, cur_sum)
return max_sum
```
2. 分治法:将序列分成左右两部分,分别求左部分、右部分和跨越中点的最大子序列和,最后将三个值取最大值。时间复杂度为 O(nlogn)。
```python
def max_subarray_sum_divide_conquer(nums):
n = len(nums)
def max_crossing_sum(nums, left, mid, right):
left_max_sum = float("-inf")
cur_sum = 0
for i in range(mid, left-1, -1):
cur_sum += nums[i]
left_max_sum = max(left_max_sum, cur_sum)
right_max_sum = float("-inf")
cur_sum = 0
for i in range(mid+1, right+1):
cur_sum += nums[i]
right_max_sum = max(right_max_sum, cur_sum)
return left_max_sum + right_max_sum
def max_subarray_sum(nums, left, right):
if left == right:
return nums[left]
mid = (left + right) // 2
left_max_sum = max_subarray_sum(nums, left, mid)
right_max_sum = max_subarray_sum(nums, mid+1, right)
crossing_max_sum = max_crossing_sum(nums, left, mid, right)
return max(left_max_sum, right_max_sum, crossing_max_sum)
return max_subarray_sum(nums, 0, n-1)
```
3. 动态规划法:定义一个变量 cur_sum,用来记录当前的连续子序列和,如果 cur_sum 小于等于 0,则从下一个元素重新开始计算,否则继续累加。用一个变量 max_sum 记录最大的连续子序列和。时间复杂度为 O(n)。
```python
def max_subarray_sum_dp(nums):
n = len(nums)
cur_sum = nums[0]
max_sum = nums[0]
for i in range(1, n):
cur_sum = max(cur_sum + nums[i], nums[i])
max_sum = max(max_sum, cur_sum)
return max_sum
```
4. Kadane算法:与动态规划法类似,但只需要一个变量 cur_sum 来记录当前的连续子序列和,不需要用一个变量 max_sum 记录最大的连续子序列和,而是在每次更新 cur_sum 的时候,同时更新最大值。时间复杂度为 O(n)。
```python
def max_subarray_sum_kadane(nums):
n = len(nums)
cur_sum = nums[0]
max_sum = nums[0]
for i in range(1, n):
cur_sum = max(nums[i], cur_sum + nums[i])
max_sum = max(max_sum, cur_sum)
return max_sum
```
这四种方法的时间复杂度分别为 O(n^2)、O(nlogn)、O(n) 和 O(n),其中 Kadane算法 是最优的。