cogito ergo sum
刷题刷得心烦！
一、问题描述：
给定一个长度为N的数组，找出一个最长的单调递增子序列（不能打乱顺序），如数组A=[5，6，7，1，2，8]，则其最长递增子序列为[5,6,7,8]，长度为4。
二、最长公共子序列法
2.1问题转换
这个问题可以转换为最长公共子序列问题。设数组A=[a1,a2,…,an],将其按从小到大的顺序排列后的数组为B=[b1,b2,…,bn]。那么数组A与数组B的最长公共子序列即是数组A的最长递增子列。
2.2算法思想
记Ai，Bi为数组A，B的前i个元素组成的数组。f(i,j)为数组Ai和Bj的最长公共子序列的长度。那么f(i,j)满足如下的递归：
if i=0 or j=0:
f(i,j)=0
else:
if ai==bj:
f(i,j)=f(i-1,j-1)+1
if ai!=bj:
f(i,j)=max(f(i,j-1),f(i-1,j))
2.3代码实现
a=raw_input().split()
b=raw_input().split()
a_len=len(a)
b_len=len(b)
f=[[0 for i in range(b_len+1)]for i in range(a_len+1)]
for index_i,i in enumerate(a):
for index_j,j in enumerate(b):
if i==j:
f[index_i+1][index_j+1]=f[index_i][index_j]+1
elif i!=j:
f[index_i+1][index_j+1]=max(f[index_i+1][index_j],f[index_i][index_j+1])
print f[a_len][b_len]
三、动态规划法
3.1算法思想
设f(i)为在数组A中以ai为结尾的最长递增子序列长度。
f(i)=max(f(j))+1 j<i and aj<ai
最终最长递增子序列为f(i)中最大的一个。
3.2代码实现
def max_array(lst):
n=len(lst)
f=[0 for i in range(n)]
for i in range(n):
max_1=0
for j in range(i):
if lst[j]<lst[i]:
if f[j]>=max_1:
max_1=f[j]
f[i]=max_1+1
return f
