把返回最长递增子序列的长度和最长递增子序列的函数分成两个函数写,并且返回最长递增子序列的函数的两个参数分别是原序列和最长递增子序列长度
时间: 2024-02-26 07:59:17 浏览: 10
好的,我可以帮你写这两个函数。下面是返回最长递增子序列的长度的函数:
```python
def get_lis_length(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
```
而下面是返回最长递增子序列及其长度的函数:
```python
def get_lis(nums):
if not nums:
return [], 0
n = len(nums)
dp = [[num] for num in nums]
lis = []
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j] and len(dp[i]) < len(dp[j]) + 1:
dp[i] = dp[j] + [nums[i]]
if len(dp[i]) > len(lis):
lis = dp[i]
return lis, len(lis)
```
这里的 `get_lis` 函数除了返回最长递增子序列的长度外,还返回了最长递增子序列本身。同时,由于最长递增子序列可能不止一个,这里在计算最长递增子序列的过程中,记录了当前找到的最长递增子序列。