最长公共子序列问题和最大子段和问题的动态规划算法实现和效率分析

最长公共子序列问题和最大子段和问题都是动态规划问题。

1. 最长公共子序列问题

最长公共子序列问题（Longest Common Subsequence, LCS）是指给定两个序列X和Y，找出它们的最长公共子序列。

动态规划算法实现：

设X={x1,x2,…,xm}和Y={y1,y2,…,yn}，令c[i][j]表示X的前i个字符和Y的前j个字符的LCS长度，b[i][j]记录c[i][j]是由哪一个子问题的解得到的。

则有以下的状态转移方程：

c[i][j] = 0, i=0 或 j=0
c[i][j] = c[i-1][j-1]+1, i,j>0 且 xi=yj
c[i][j] = max(c[i-1][j], c[i][j-1]), i,j>0 且 xi≠yj

实现代码如下：

def LCS(X, Y):
    m, n = len(X), len(Y)
    c = [[0]*(n+1) for i in range(m+1)]
    b = [[0]*(n+1) for i in range(m+1)]
    for i in range(1, m+1):
        for j in range(1, n+1):
            if X[i-1] == Y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
                b[i][j] = '↖'
            elif c[i-1][j] >= c[i][j-1]:
                c[i][j] = c[i-1][j]
                b[i][j] = '↑'
            else:
                c[i][j] = c[i][j-1]
                b[i][j] = '←'
    return c, b

def printLCS(b, X, i, j):
    if i == 0 or j == 0:
        return
    if b[i][j] == '↖':
        printLCS(b, X, i-1, j-1)
        print(X[i-1], end='')
    elif b[i][j] == '↑':
        printLCS(b, X, i-1, j)
    else:
        printLCS(b, X, i, j-1)

效率分析：

设X和Y的长度分别为m和n，时间复杂度为O(mn)，空间复杂度也为O(mn)。

2. 最大子段和问题

最大子段和问题（Maximum Subarray Sum）是指在一个数列中找到一个连续的子序列，使得该子序列的和最大。

动态规划算法实现：

设a[1..n]为输入的数组，sum[i]表示以a[i]为结尾的最大子段和，则有以下的状态转移方程：

sum[1] = a[1]
sum[i] = max(sum[i-1]+a[i], a[i]), i>1

实现代码如下：

def maxSubarray(a):
    n = len(a)
    dp = [0] * n
    dp[0] = a[0]
    for i in range(1, n):
        dp[i] = max(dp[i-1] + a[i], a[i])
    return max(dp)

效率分析：

设a的长度为n，时间复杂度为O(n)，空间复杂度为O(n)。

综上所述，最长公共子序列问题和最大子段和问题的动态规划算法都是时间复杂度为O(n^2)，空间复杂度为O(n^2)的算法，但是两者的状态转移方程和实现方式不同。