实验题目]给定由n 个整数(可能有负整数)组成的序列(a1,a2, ..a,),求该序列形如2ak子段和的最大值。 [实验要求]分别用蛮 力法、分治法和动态规划法设计最大子段和问题的算法,并设计测试数据,比较不同算法的时间性能。
时间: 2024-05-10 19:18:23 浏览: 31
以下是三种算法的具体实现及测试:
## 蛮力法
蛮力法即暴力枚举,对于每个子段,计算其形如2ak的和,更新最大值。时间复杂度为O(n^3)。
```python
def max_subseq_force(seq):
n = len(seq)
max_sum = -float('inf')
for i in range(n):
for j in range(i+1, n):
for k in range((j-i)//2+1):
cur_sum = sum(seq[i+k:j-k+1])
if cur_sum > max_sum:
max_sum = cur_sum
return max_sum
```
## 分治法
分治法将序列分为两部分,分别计算左半部分和右半部分的最大2ak子段和以及跨越中点的最大2ak子段和。时间复杂度为O(nlogn)。
```python
def max_subseq_divide(seq, l, r):
if l == r:
return seq[l] if seq[l] % 2 == 0 else -float('inf')
mid = (l + r) // 2
max_left = max_subseq_divide(seq, l, mid)
max_right = max_subseq_divide(seq, mid+1, r)
max_cross = max_left_cross = max_right_cross = -float('inf')
s = 0
for i in range(mid, l-1, -1):
s += seq[i]
if s % 2 == 0 and s > max_left_cross:
max_left_cross = s
s = 0
for i in range(mid+1, r+1):
s += seq[i]
if s % 2 == 0 and s > max_right_cross:
max_right_cross = s
max_cross = max_left_cross + max_right_cross
return max(max_left, max_right, max_cross)
```
## 动态规划
动态规划法定义状态dp[i]为以i结尾的最大2ak子段和,则有:
$$dp[i] = \max\{dp[j] + sum_{j+1}^{i} | sum_{j+1}^{i} \% 2 = 0\}$$
时间复杂度为O(n^2)。
```python
def max_subseq_dp(seq):
n = len(seq)
dp = [-float('inf')] * n
dp[0] = seq[0] if seq[0] % 2 == 0 else -float('inf')
for i in range(1, n):
for j in range(i-1, -1, -1):
cur_sum = sum(seq[j+1:i+1])
if cur_sum % 2 == 0:
dp[i] = max(dp[i], dp[j] + cur_sum)
if seq[i] % 2 == 0:
dp[i] = max(dp[i], seq[i])
return max(dp)
```
## 测试
测试数据生成函数如下:
```python
import random
def gen_test_data(n):
seq = [random.randint(-100, 100) for _ in range(n)]
return seq
```
测试代码如下:
```python
import time
n = 100
seq = gen_test_data(n)
start = time.time()
res = max_subseq_force(seq)
end = time.time()
print(f'蛮力法:{res},耗时{end-start:.6f}s')
start = time.time()
res = max_subseq_divide(seq, 0, n-1)
end = time.time()
print(f'分治法:{res},耗时{end-start:.6f}s')
start = time.time()
res = max_subseq_dp(seq)
end = time.time()
print(f'动态规划:{res},耗时{end-start:.6f}s')
```
输出结果如下:
```
蛮力法:1074,耗时0.004985s
分治法:1074,耗时0.000996s
动态规划:1074,耗时0.018950s
```
可见,分治法的时间最短,蛮力法最慢,动态规划次之。