最长上升子序列python
时间: 2023-09-24 11:07:21 浏览: 65
最长上升子序列是指在一个给定序列中,找到一个最长的子序列,使得子序列中的元素是严格递增的。下面是一个用Python实现最长上升子序列的例子:
```python
def longest_increasing_subsequence(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)
nums = [10, 9, 2, 5, 3, 7, 101, 18]
result = longest_increasing_subsequence(nums)
print(result)
```
这段代码中,我们使用动态规划的思想,定义一个dp数组,dp[i]表示以第i个元素结尾的最长上升子序列的长度。初始时,每个元素自成一个长度为1的上升子序列。然后,我们遍历数组,对于每个元素nums[i],通过比较nums[i]与之前的元素nums[j]的大小关系,更新dp数组中的值。最后,返回dp数组中的最大值即可。在给定的例子中,最长上升子序列是[2, 3, 7, 101],其长度为4。
相关问题
最长不上升子序列python
以下是一个使用动态规划的Python程序,用于查找最长不上升子序列:
def longest_non_increasing_subsequence(arr):
n = len(arr)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if arr[j] >= arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
arr = [5, 2, 8, 6, 3, 6, 9, 7]
print(longest_non_increasing_subsequence(arr)) # 输出为 4
该程序的时间复杂度为O(n^2),其中n是序列的长度。
二分法最长上升子序列
二分法最长上升子序列问题是一个经典的动态规划问题。它的解决方法并不是使用二分法,而是利用动态规划的思想。
首先,我们定义一个数组 dp,其中 dp[i] 表示以第i个元素结尾的最长上升子序列的长度。初始化时,将 dp 数组的所有元素都设为1。
然后,我们遍历数组,并对于每个元素 nums[i],再遍历其前面的所有元素 nums[j](其中 0 ≤ j < i)。如果 nums[i] 大于 nums[j],则更新 dp[i] 的值为 dp[j] + 1,表示以第i个元素结尾的最长上升子序列的长度比以第j个元素结尾的最长上升子序列的长度多1。
最后,遍历 dp 数组,找到其中的最大值,即为所求的最长上升子序列的长度。
以下是一个示例代码实现:
```python
def lengthOfLIS(nums):
if len(nums) == 0:
return 0
dp = [1] * len(nums)
max_length = 1
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j]:
dp[i] = max(dp[i], dp[j] + 1)
max_length = max(max_length, dp[i])
return max_length
```
希望对你有所帮助!如果还有其他问题,请继续提问。