I am trying to find topic algorithm and am stuck. Basically, I adopted the code given in zzz's answer here, which is Longest Increasing Subsequence algorithm, to get Longest Non-decreasing Subsequence. What I aim to find is LNDS that has a minimal sum (MSLNDS) and don't know do I have one. But as far as I can tell, original LIS algorithm as presented on wikipedia does locate minimal sum LIS. Docstring of its code says that LIS algorithm guarantees that if multiple increasing subsequences exist, the one that ends with the smallest value is preferred, and if multiple occurrences of that value can end the sequence, then the earliest occurrence is preferred. Don't know what earliest occurrence means, but would love not to be in the position to generate all LNDS to find my MSLNDS. It seems to me that clever transformation given by templatetypedef may be used to show that unique MSLIS transforms to MSLNDS, but dont have the proof. So,
a) Will LIS algorithm as given on wikipedia always output minimal sum LIS?
b) If LIS algorithm is adopted this way, will LNDS algorithm retain this property?
def NDS(X):
n = len(X)
X = [0.0] + X
M = [None]*(n+1)
P = [None]*(n+1)
L = 0
for i in range(1,n+1):
#########################################
# for LIS algorithm, this line would be
# if L == 0 or X[M[1]] >= X[i]:
#########################################
if L == 0 or X[M[1]] > X[i]:
j = 0
else:
lo = 1
hi = L+1
while lo < hi - 1:
mid = (lo + hi)//2
#########################################
# for LIS algorithm, this line would be
# if X[M[mid]] < X[i]:
#########################################
if X[M[mid]] <= X[i]:
lo = mid
else:
hi = mid
j = lo
P[i] = M[j]
if j == L or X[i] < X[M[j+1]]:
M[j+1] = i
L = max(L,j+1)
output = []
pos = M[L]
while L > 0:
output.append(X[pos])
pos = P[pos]
L -= 1
output.reverse()
return output
