最长递增序列
1.1 最长递增子序列
从一个给定的序列中找出一个最长的序列，该序列从小到大进行排序。比如：一个给定的序列如下所示：0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15
那么，它的最长子序列就是：0, 2, 6, 9, 11, 15
一种思路如下图，首先组合出所有的可能序列，然后从最长的序列开始，逐步减小为1，找最大的递增子序列，这种方法的时间复杂度较高，如下所示：
另一种思路就是动态规划：比如针对序列：{3,2,6,4,5,1}，存储在数组D中，设L[i]存储以第i个元素结尾是的最大序列，则有:
L[0] = [3] L[1] = [2] L[2] = [2,6] L[3] = [2,4] L[4] = [2,4,5] L[5] = [1]
使用动态规划的思想，主要是考虑L[i]目前已经求得的L[0]至L[i-1]的基础上进行，判断条件是：
L[i] = max(L[j] | j<i ,D[j]< D[i]) +"D[i]"
代码如下：
class Solution:
def lengthOfLIS(self, nums):
if len(nums)==0:
return 0
L = [[] for i in range(len(nums))]
L[0] = [nums[0]]
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j] and len(L[i]) < (len(L[j])+1):
L[i] = L[j][:]
L[i].append(nums[i])
max_len = 0
for i in L:
if len(i)>max_len:
max_len = len(i)
return max_len 通过上面的结果可以发现，L[2]不是[3,6]，而是[2,6]，这是因为代码中j遍历的时候，先得到[3,6],之后被[2,6]覆盖了。
以上代码虽然通过了leetcode-300-最长上升子序列所有的测试用例，但是会超出时间限制。原因主要是，L中保存了具体的以i结尾的最长序列，而题目要求的是最大长度，因此可以修改如下。
修改：使用dp保存 以第i个元素结尾的最大长度 ，其余部分不变，如下所示：
class Solution:
def lengthOfLIS(self, nums):
if len(nums)==0:
return 0
dp = [1 for i in range(len(nums))]
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j]and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
return max(dp) 进阶：保存具体的最长子序列
class Solution:
def lengthOfLIS(self, nums):
if len(nums)==0:
return 0
dp = [1 for i in range(len(nums))]
L = [[] for i in range(len(nums))]
L[0] = [nums[0]]
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j] and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
L[i] = L[j][:] # 更新L[i]。
L[i].append(nums[i]) # 注意，这里需要在遍历里层循环结束之后，将第i个元素的值插入到最后。
print(L)
return max(dp) 输入：[2,5,3,7] 输出: [[2], [2, 5], [2, 3], [2, 5, 7]]
问题：结果中输出的最长序列为[2,5,7]，而[2,3,7]也是最长序列。通过分析发现，当i等于3时（也就是i指向7），此时当j指向5时，由于5<7，而此时的dp[3]=2,dp[1]=2,因此更新之后dp[3]=3,而当j指向3的时候，由于dp[j]+1=dp[i]，因此，不进行更新，从而导致L中只保存了[2,5,7]，所以关键问题在于当dp[j]+1=dp[i]时，如何保存多个最大序列。
进阶：输出所有最长序列
class Solution:
def lengthOfLIS(self, nums):
if len(nums)==0:
return 0
dp = [1 for i in range(len(nums))]
for i in range(1, len(nums)):
for j in range(i):
if nums[i] > nums[j] and dp[i] < dp[j] + 1:
dp[i] = dp[j] + 1
print(dp) # [1,1,2,2,2,3]
max_len = max(dp)
L = [[] for i in range(max_len)] # [[2,1], [5,4,3], [6]]
# 保存dp中对应长度的数值。
for i in range(len(dp)):
L[dp[i]-1].append(nums[i])
print(L)
result = []
def helper(i, res):
if len(res) == max_len:
result.append(res.copy())
return
for k in range(len(L[i])):
res.append(L[i][k])
helper(i+1, res)
res.pop()
helper(0, [])
return dp, max(dp),result 思路：比如针对输入[2,1,5,4,3,6],对应的dp输出为[1,1,2,2,2,3]。由于dp中保存的是以该位置为结尾时的最大长度。因此可以首先输出dp中长度为3的位置的元素，然后输出长度为2的元素，然后在输出长度为1的元素，之后逆序就可以得到对应的最长序列。
但是从dp中可以看出，长度为1序列有2个，长度为2的序列就有2*3为6个，长度为3的序列就为2*3*1为6个，要想输出所有的序列，那么需要进行组合。
首先，根据dp中不同值，将对应nums值存储在L中，可以得到[[2, 1], [5, 4, 3], [6]]，含义就是[2,1]表示以2或者1结尾的元素长度为1，[5,4,3]就是以5或4或3结尾的最大序列长度为2，以此类推。
接着，每次从L中每一项取一个元素，然后组合在一起成最大序列，此时就是一种最大序列的组合。考虑使用深度递归方法，输出所有组合如下：[[2, 5, 6], [2, 4, 6], [2, 3, 6], [1, 5, 6], [1, 4, 6], [1, 3, 6]]，这就是所有的组合。 --2020-09-21.【S 后续可以继续整理，添加图片和规范说明，整理到blog中】
【注意】可以看一下《算法分析与设计》中的相关代码，上面的代码应该还存在一定的问题，觉得最好是求最优值（最长公共子序列长度），之后求最优解（最长公共子序列），这样比较符合动态规划的解题过程。
1.2 最长连续递增序列
思路：如果nums[i]大于nums[i-1],此时就max_i+1,max_i表示以i结尾的最大连续序列长度。然后比较max_i与max_len，将最大的长度保存到max_len中。如果nums[i]小于nums[i-1]，此时表示连续递增断开，需要重新开始，因此max_i=1.
class Solution:
def findLengthOfLCIS(self, nums):
if len(nums)==0:
return 0
n = len(nums)
max_len = 1
for i in range(n):
if i == 0:
max_i = 1
else:
if nums[i] > nums[i - 1]:
max_i += 1
else:
max_i = 1
max_len = max(max_len, max_i)
return max_len 进阶：存储最长的连续递增子序列。L保存所有的连续递增序列，tmp保存当前的连续递增序列。由于当nums[i]小于nums[i-1]的时候，相当于重新开始，因此此时将tmp结果保存到L中。
class Solution:
def findLengthOfLCIS(self, nums):
if len(nums)==0:
return 0
n = len(nums)
max_len = 1
L = []
tmp = []
for i in range(n):
if i == 0:
max_i = 1
tmp.append(nums[i])
else:
if nums[i] > nums[i - 1]:
max_i += 1
else:
L.append(tmp)
tmp = []
max_i = 1
tmp.append(nums[i])
max_len = max(max_len, max_i)
L.append(tmp)
return max_len, L
# s = Solution()
# nums = [2,2,2,2,2]
# print(s.findLengthOfLCIS(nums)) 
字节跳动一面208人在聊
投递腾讯等公司8个岗位