document.write('

方法一：最长公共子串法

对序列L=＜a1,a2,...,an＞按递增进行排序得到序列LO=＜b1,b2,...,bn＞。显然，L与LO的最长公共子序列就是L的最长递增子序列。因此，可以使用

求公共子序列的方法来求解。

方法二：动态规划法

由于以第i个元素为结尾的最长递增子序列只与以第i-1个元素为结尾的最长递增子序列有关，因此，本题可以采用动态规划的方法来解决。下面首先

介绍动态规划方法中的核心内容递归表达式的求解。

以第i个元素为结尾的最长递增子序列的取值有两种可能：

(1)1，第i个元素单独作为一个子串(L[i]＜=L[i-1])；

(2)以第i-1个元素为结尾的最长递增子序列加1(L[i]＞L[i-1])。

由此可以得到如下的递归表达式：假设maxLen[i]表示以第i个元素为结尾的最长递增子序列，那么

(1)maxLen [i]=max[1, maxLen [j]+1], j＜i and L[j]＜L[i]

(2)maxLen[0]=1

根据这个递归表达式可以非常容易地写出实现的代码：

#函数功能: 求字符串L的最长递增子串的长度

def getMaxAscendingLen(strs):

lens=len(strs)

maxLen=[None]*lens

maxLen[0]=1

maxAscendingLen=1

i=1

while i＜lens:

maxLen[i]=1# maxLen[i]的最小值为1;

j=0

while j＜i:

if list(strs)[j]＜list(strs)[i] and maxLen[j]＞maxLen[i]-1:

maxLen[i]=maxLen[j]+1

maxAscendingLen=maxLen[i]

j+=1

i+=1

return maxAscendingLen

if __name__=="__main__":

s="xbcdza"

print "最长递增子序列的长度为:"+str(getMaxAscendingLen(s))

程序的运行结果为：

xbcdza最长递增予序列的长度为：4

算法性能分析：

由于这种方法用双重循环来实现，因此，这种方法的时间复杂度为O(N2)，此外由于这种方法还使用了N个额外的存储空间，因此，空间复杂度为O(N)。

');