最大公共子数组问题

最大公共子数组问题(分治法)

原理:

采用二分法,分别找出左边数组的最大值,右边数组的最大值,再找出带有中间元素的最大值

image-20220503182312517

S1:数组X[1,n/2]中的最大值

S2:数组X[n/2+1, n]的最大值

S3:包含中间元素的最大值

image-20220503191705210

算法实例:

分解:

image-20220503182816198

归并:

image-20220503191605979

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
'''
最大子数组问题(分治法)
这里主要分为三个部分
1.求二分之后左边和右边的最大值
2.求合并之后的最大值
3.上面三者比较取最大值
'''

def max_sub(X, start, end):
# 如果只有一个数字的话那么最大子数组就是它本身
if start == end:
return X[start]

# 记录一下中间位置
mid = int((start + end)/2)

# 获取左边最大子数组
left = max_sub(X, start, mid)
# 获取右边最大子数组
right = max_sub(X, mid+1, end)

# 获取合并之后的最大子数组
merge = get_merge(X, start, mid, end)

# 判断一下左边右边中间那个数值最大就返回那个数值
if left > right:
if right > merge:
return left
elif left > merge:
return left
else:
return merge
else:
if left > merge:
return right
elif right > merge:
return right
else:
return merge


def get_merge(X, start, mid, end):
# 左边包含中间的最大值
max_left = X[mid]
# 左边辅助计算的最大值
temp_max_left = X[mid]

# 右边最大值
max_right = X[mid+1]
# 右边辅助计算的最大值
temp_max_right = X[mid+1]

# 计算左边的最大值
for i in range(mid-1, start-1, -1):
if max_left <= temp_max_left + X[i]:
max_left = temp_max_left + X[i]
temp_max_left += X[i]

# 计算右边的最大值
for i in range(mid+2, end+1):
if max_right <= temp_max_right + X[i]:
max_right = temp_max_right + X[i]
temp_max_right += X[i]

return max_right + max_left

# 测试数据
X = [-1,-3,3,5,-4,3,2,-2,3,6]
length = len(X)-1
max_num = max_sub(X, 0, length)
print(max_num)

最大公共子数组(动态规划)

image-20220508155220309

使用动态规划来进一步的进行时间复杂度的缩减

我们在求解最大子数组的问题的时候,先要看一下以i开头的子数组的最大值

image-20220508155302176

我们可以把上面情况风味两种,第一种:D123,第二种D456

D2 = x[2] + D3

D1 = x[1] + D2

image-20220508155337340

当我们算D3的时候

x[3] + D4 < x[3] 这样就导致我们D3不能够使用上述方法,

所以我们在使用上述公式的时候,要分为两种情况:

image-20220508155357853

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
'''
最大子数组问题 动态规划
这里主要分为部分:
1. 遍历一遍原始数组
2. 在便利的同时创建D数组 D[i]数组 ==> 以i开头的最大子数组
3. 创建rec追踪数组,rec[i] 表示以i开头 以rec[i] 结尾的最大子数组
'''

def get_max_num(X, D, Rec):
# 先初始化D 和 Rec 数组
i = len(X)-1
D[i] = X[i]
Rec[i] = i
# 从后往前遍历整个数组
for i in range(len(X)-2,-1,-1):

# 如果第i位置的数据大于 第i个位置+D[i+1] 我们就把D[i]设置为X[i]
if X[i] > X[i] + D[i+1]:
D[i] = X[i]
Rec[i] = i
# 如果第i位置的数据小于于第i个位置+D[i+1] 我们就把D[i]设置为X[i]
else:
D[i] = X[i] + D[i+1]
Rec[i] = Rec[i+1]
return

X = [-1,-3,3,5,-4,3,2-2,3,6]
D = [0 for i in range(len(X))]
Rec = [0 for i in range(len(X))]

get_max_num(X, D, Rec)