算法实现 算法实现 最大公共子数组问题 Nuyoah 2022-05-05 2022-11-21 最大公共子数组问题(分治法)
原理:
采用二分法,分别找出左边数组的最大值,右边数组的最大值,再找出带有中间元素的最大值
S1:数组X[1,n/2]中的最大值
S2:数组X[n/2+1, n]的最大值
S3:包含中间元素的最大值
算法实例:
分解:
归并:
代码:
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)
最大公共子数组(动态规划)
使用动态规划来进一步的进行时间复杂度的缩减
我们在求解最大子数组的问题的时候,先要看一下以i开头的子数组的最大值
我们可以把上面情况风味两种,第一种:D123,第二种D456
D2 = x[2] + D3
D1 = x[1] + D2
当我们算D3的时候
x[3] + D4 < x[3] 这样就导致我们D3不能够使用上述方法,
所以我们在使用上述公式的时候,要分为两种情况:
代码
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 ): i = len (X)-1 D[i] = X[i] Rec[i] = i for i in range (len (X)-2 ,-1 ,-1 ): if X[i] > X[i] + D[i+1 ]: D[i] = X[i] Rec[i] = 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)