求最长交替序列长度的动态算法

Question

LetA=be一个数列，其中n >0，每个数ai∈{0,1}。一个subsequencethen<0>、<1>、<0，1>、<1，0>and<0，1，0，1，0>are不同的交替subsequenceswhile<1，1>is不是交替的子序列。Is<0，1，0，1，0>and的最长交替子序列，长度为5。

(a)设计一个O(n^2)动态规划算法来求给定序列A的最长交替序列的长度

(b)设计一个O(n)动态规划算法，求出给定序列A的最长交替序列的长度。

Answer 1

我认为你不需要DP解决方案来解决这个问题。

对于这一点，贪婪方法以最直接的方式工作。总结:由于列表只包含[0,1]，您只需要检查序列中的值更改了多少次；这就是您的最大交替子序列的长度。

时间复杂度: O(N)

以下是工作代码：

count = 1
ll = [0,1,0,0,0,1,0]
lval = ll[0]
for item in ll[1:]:
    if item != lval:
        count += 1
        lval = item

print(count)

输出：

5

编辑

如果您仍在寻找DP解决方案，这里是O(N)解决方案：

索引Di表示最大交替子序列的长度，直到最后一个值为i j的索引i

ll = [0,1,0,0,0,1,0]

D = [[0,0] for _ in range(len(ll))]

D[0][0] = 1 if ll[0] == 0 else 0
D[0][1] = 1 - D[0][0]

for i in range(1, len(ll)):
    D[i][ll[i]] = max(1 + D[i-1][1-ll[i]], D[i-1][ll[i]])
    D[i][1-ll[i]] = D[i-1][1-ll[i]]

print(max(D[-1]))ll = [0,1,0,0,0,1,0]

D = [[0,0] for _ in range(len(ll))]

D[0][0] = 1 if ll[0] == 0 else 0
D[0][1] = 1 - D[0][0]

for i in range(1, len(ll)):
    D[i][ll[i]] = max(1 + D[i-1][1-ll[i]], D[i-1][ll[i]])
    D[i][1-ll[i]] = D[i-1][1-ll[i]]

print(max(D[-1]))