JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2010, Vol. 40 ›› Issue (6): 156-158.

• Articles • Previous Articles    

An algorithm for computing  the all longest increasing subsequence

YANG Hai-bin, ZHAO Xue-feng, WANG Xiu-hua, ZHANG Li-xiang   

  1. College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, China
  • Received:2009-10-20 Online:2010-12-16 Published:2009-10-20

PDF (PC)

1408

Abstract:

The  Cover-Making(CM) algorithm of the longest increasing subsequence was analyzed, and  a new algorithm that can compute a sequence’s all longest increasing subsequences was presented, based on the CM algorithm. The complexity of the time isO((m+1)k+(n-k)log k), and the complexity of the space is O(n+km).

Key words: subsequence, CM algorithm, longest increasing subsequence, all longest increasing subsequence

[1] ZHU Na-na1, 2, ZHANG Hua-xiang1, 2*, LIU Li1, 2. Automatic image annotation based on approved FCM algorithm and Bayesian classification [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2013, 43(6): 12-16.
[2] MA Qing, LI Qiqiang*. Public buildings baseline load forecasting based on demand
response in electric power [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2011, 41(2): 114-118.
[3] ZHANG Cheng-hui,NING Yong,JI Peng . Improved FCM clustering algorithm and its application inred tide prediction [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2007, 37(6): 1-4 .
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd