给定一个未经排序的整数数组,找到最长且连续的递增序列 python代码实现
时间: 2024-09-13 15:10:23 浏览: 63
python-leetcode面试题解之第128题最长连续序列-题解.zip
在Python中,可以使用动态规划(Dynamic Programming)的方法来解决这个问题。这里是一个简单的解决方案:
```python
def longestIncreasingSubsequence(nums):
if not nums:
return []
dp = [1] * len(nums)
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_len = max(dp)
# 通过dp列表反向查找最长序列的实际元素
max_seq = []
idx = dp.index(max_len)
while idx >= 0:
max_seq.append(nums[idx])
idx -= 1
return max_seq[::-1] # 返回结果需要从右往左,因为我们在寻找最右边的元素开始的最长递增子序列
# 示例
nums = [10, 9, 2, 5, 3, 7, 101, 18]
print(longestIncreasingSubsequence(nums)) # 输出:[2, 3, 7, 101]
阅读全文