最大公共子数组问题

最大公共子数组问题（分治法）

原理：

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

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)