python - 为什么我找到最长的递增子序列而不是最长的递减子序列?
问题描述
我试图在 O(nlogn) 的数组中寻找最长的递减子序列。不确定这是否真的需要 O(nlogn),但无论如何这会返回最长递增子序列的长度,而不是最长递减子序列的长度。任何人都可以帮忙吗?!?
def binary_search(L, l, r, key):
while (r - l > 1):
m = l + (r - l)//2
if (L[m] >= key):
r = m
else:
l = m
return r
def LongestDecreasingSubsequenceLength(L, size):
tailTable = [0 for i in range(size + 1)]
len = 0
tailTable[0] = L[0]
len = 1
for i in range(1, size):
if (L[i] < tailTable[0]):
# new smallest value
tailTable[0] = L[i]
elif (L[i] > tailTable[len-1]):
tailTable[len] = L[i]
len+= 1
else:
tailTable[binary_search(tailTable, -1, len-1, L[i])] = L[i]
return len
L = [ 38, 20, 15, 30, 90, 14, 6, 7]
n = len(L)
print("Length of Longest Decreasing Subsequence is ",
LongestDecreasingSubsequenceLength(L, n))
解决方案
如果您愿意以任何方式看待它,维基百科有一些伪代码很容易转移到 Python 中并翻转以减少子序列。
N = len(X)
P = np.zeros(N, dtype=np.int)
M = np.zeros(N+1, dtype=np.int)
L = 0
for i in range(0, N-1):
# Binary search for the largest positive j ≤ L
# such that X[M[j]] <= X[i]
lo = 1
hi = L
while lo <= hi:
mid = (lo+hi)//2
if X[M[mid]] >= X[i]:
lo = mid+1
else:
hi = mid-1
# After searching, lo is 1 greater than the
# length of the longest prefix of X[i]
newL = lo
# The predecessor of X[i] is the last index of
# the subsequence of length newL-1
P[i] = M[newL-1]
M[newL] = i
#print(i)
if newL > L:
# If we found a subsequence longer than any we've
# found yet, update L
L = newL
# Reconstruct the longest increasing subsequence
S = np.zeros(L, dtype=np.int)
k = M[L]
for i in range(L-1, -1, -1):
S[i] = X[k]
k = P[k]
S
这给出了你所追求的序列
array([38, 20, 15, 14, 6])
推荐阅读
- microsoft-graph-api - 无法使用 Graph API 读取本地用户日历。错误 401 未经授权
- javascript - 如何在 DataTables 中获取搜索输入?
- r - 将 data.table 的每个单元格乘以预先指定范围内的不同因子
- r - X 和 y 长度不同,绘制序数逻辑回归模型的部分效应
- php - 如何创建单独的文件夹以将每个上传的文件存储在 php 中?
- html - “NoRowsOverlay”或“overlayNoRowsTemplate”位置超出 ag-grid 列或重叠标题
- python - cross_val_score 和 KFold 的区别
- selenium - Selenium driver.find_elements_by_xpath 遇到问题
- python - 使用 timedelta 减少 5 分钟
- javascript - 3D 对象在我的网站中显示为黑色背景